After enjoying the brilliant light show, everyone was attracted to the block-clearing game area nearby.

Colorful blocks are neatly arranged on the table. Little T and Little S, as the stall owners, each provide a magic sieve that can clear blocks in batches. The rules of the game are simple: you can repeatedly use these two sieves to clear blocks, and the final ranking is based on the total number of blocks remaining on the table.

There are $n$ piles of blocks neatly arranged on the table, with the initial number of blocks in the $i$-th pile ($1 \le i \le n$) being $a_i$.

Little T and Little S each provide a magic sieve with mesh sizes $p$ and $q$, respectively, which can clear blocks in batches by taking the modulo of the number of blocks in the covered piles. When naturally deployed, both sieves span exactly $k$ piles of blocks. They have special elasticity, allowing them to be stretched freely to both ends to cover a longer range, but they cannot be compressed inward. The magic sieves are used as follows:

• Select a continuous interval of blocks $[l, r]$ with a length of at least $k$ and place the sieve over it;
• Choose one of the two magic sieves, i.e., select $m \in \{p, q\}$;
• For every pile of blocks in the interval $[l, r]$, take the modulo of its quantity by $m$, i.e., set $a_i \leftarrow a_i \pmod m$.

Since you are participating in this game, you are naturally not satisfied with mediocre results. To top the leaderboard, you want to know the minimum total number of blocks remaining on the table (i.e., $\sum_{i=1}^n a_i$) that can be achieved by repeatedly using the magic sieves any number of times.

Input

Each test case contains multiple test data. The first line of the input contains a positive integer $T$ ($1 \le T \le 10^3$), representing the number of test cases. For each test case:

• The first line contains four positive integers $n, k, p, q$ ($1 \le k \le n \le 10^5$, $1 \le p < q \le 10^9$), representing the number of piles of blocks, the number of piles spanned by the sieve when naturally deployed, and the mesh sizes of the two magic sieves, respectively.
• The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), representing the initial number of blocks in each pile.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output a single non-negative integer representing the minimum total number of blocks remaining on the table.

Examples

Input 1

6
1 1 3 4
2
3 2 10 20
31 41 59
4 3 3 4
1 2 3 4
6 4 9 20
18 27 180 9 45 99
7 4 3 5
6 7 14 12 100 78 4
9 4 244 353
9982 4435 3998 2443 5399 8244 3539 9824 4353

Output 1

1
11
3
0
4
569

Note

For the second test case, one way to achieve the minimum total of 11 blocks remaining on the table is as follows:

• Select the interval $[1, 3]$ and use the magic sieve with a mesh size of 10; the remaining block counts become $[1, 1, 9]$.

For the third test case, one way to achieve the minimum total of 3 blocks remaining on the table is as follows:

• Select the interval $[2, 4]$ and use the magic sieve with a mesh size of 4; the remaining block counts become $[1, 2, 3, 0]$;
• Select the interval $[1, 3]$ and use the magic sieve with a mesh size of 3; the remaining block counts become $[1, 2, 0, 0]$.