Casual gamer Little Q has not only achieved excellent results in algorithm competitions but also ranks highly in a diamond-collecting game.

There are $n$ different types of diamonds in this game, numbered from 1 to $n$. Little Q has been playing this game for a long time, and for the $i$-th type of diamond, he has already collected $a_i$ units. The biggest highlight of this game is that there is only one way to obtain diamonds: purchasing them from the shop. Specifically, the unit price of the $i$-th type of diamond is $b_i$ coupons. To encourage players to top up, there is no upper limit on the quantity of each type of diamond; as long as one is willing to spend money, one can own any number of diamonds. However, this game does not have a "discard item" feature, so Little Q cannot complete the task by discarding diamonds.

Recently, the game launched a limited-time achievement task. Players who complete the task can receive an honorary title. The condition for completing the task is: given positive integers $k$ and $m$, for any integer $x$ ($2^k \le x \le n$), the sum $a_x + a_{\lfloor \frac{x}{2} \rfloor} + a_{\lfloor \frac{x}{4} \rfloor} + a_{\lfloor \frac{x}{8} \rfloor} + \dots + a_{\lfloor \frac{x}{2^k} \rfloor}$ must be a multiple of $m$.

High-level player Little Q naturally wants to complete this limited-time achievement task, but before spending money, he wants to know exactly how many coupons he needs to complete this task. Please write a program to help Little Q calculate the minimum number of coupons required.

Input

The first line contains a positive integer $T$, representing the number of test cases.

Each test case starts with a line containing 9 positive integers $n, k, m, p, SA, SB, SC, A, B$, where $n$ represents the number of diamond types, and $k, m$ represent the task conditions.

To reduce the input size to some extent, $a[]$ and $b[]$ are generated by the following code:

unsigned int SA, SB, SC;int p, A, B;
unsigned int rng61(){
    SA ^= SA << 16;
    SA ^= SA >> 5;
    SA ^= SA << 1;
    unsigned int t = SA;
    SA = SB;
    SB = SC;
    SC ^= t ^ SA;
    return SC;
}
void gen(){
    scanf("%d%d%d%d%u%u%u%d%d", &n, &k, &m, &p, &SA, &SB, &SC, &A, &B);
    for(int i = 1; i <= p; i++)scanf("%d%d", &a[i], &b[i]);
    for(int i = p + 1; i <= n; i++){
        a[i] = rng61() % A + 1;
        b[i] = rng61() % B + 1;
    }
}

Output

For each test case, output a single integer on a new line, representing the minimum number of coupons required.

Examples

Input 1

2
3 1 2 3 11111 22222 33333 1 1
1 5
2 3
3 6
7 2 3 7 11111 22222 33333 1 1
6 9
4 5
3 7
5 2
2 4
1 7
9 6

Output 1

3
14

Constraints

• $1 \le T \le 10$
• $1 \le k \le 10$ and $2^k \le n$
• $1 \le p \le \min(n, 100000)$, $10000 \le SA, SB, SC \le 1000000$
• $1 \le A, B, a_i, b_i \le 10^7$

Subtasks

• Subtask 1 (30 points): Satisfies $1 \le n \le 1000$ and $m = 2$.
• Subtask 2 (40 points): Satisfies $1 \le n \le 10^5$ and $m \le 200$.
• Subtask 3 (30 points): Satisfies $1 \le n \le 10^7$ and $m \le 200$.