You are the operator of a crane. In the reach of the crane there are N locations numbered from 0 to N-1. Initially the location 0 is empty and each of the other locations contains a box with the respective number (i.e. the box in the location i has the number i).

You were assigned a task to rearrange the boxes to form a special top-secret configuration. Because of the secrecy the configuration had to be transferred in a special way that only you can understand.

The secret configuration is characterized by five numbers q, p, m, d and M. To find out the final box locations you should follow this procedure: Consider the boxes in the order of their numbers. (I.e. the box number 1 comes first, the block number 2 second, etc.) The final location for the i-th box will have the number p_i= (c_i + d * x + y) mod N, where:

1. Numbers c_i are defined by the recurrence equation: c₀ = 0, c_i + 1 = (c_i * q + p) mod m.
2. Numbers x and y are non-negative integers chosen in such a way that p_i ≠ M and no previous box was assigned to the location p_i.
3. If there are more choices for x and y satisfying conditions 1 and 2, choose the one that minimizes y.
4. If there are more choices for x and y satisfying conditions 1, 2 and 3, choose the one that minimizes x.

Once you find the secret configuration, you are supposed to rearrange the boxes accordingly. Unfortunately there is almost no room to manipulate the boxes. The only operation you are able to do is to lift a box with the crane and drop it on the location that is currently empty. (Note that there will always be exactly one empty location.)

There is one more problem. The whole operation is extremely time-critical and it is imperative that you should achieve the final configuration as soon as possible – i.e. you must reach it using the minimal number of box moves.

Task specification

Given the numbers N, M, q, p, m and d, determine how many described operations (lifting a box and dropping it to the free location) are sufficient and necessary to reach the configuration determined using the procedure above.

Input

On the first line of input file there is one number T – the number of test cases. [T ≤ 7000] T lines follow, each of them describing one test case. On each of these lines there are six numbers N, M, q, p, m and d separated by spaces. [N, M, d ≤ 1000000] [q, p, m ≤ 10000]

Output

For each test case output one line containing the number of operations sufficient and necessary to reach the final configuration.

Example

Input:
1
8 3 5 2 7 4

Output:
6

The recurrence gives the values c₁ = 2, c₂ = 5, c₃ = 6, c₄ = 4, c₅ = 1, c₆ = 0 and c₇ = 2. The secret configuration is: Box 6 on the location 0, box 5 on the location 1, box 1 on the location 2, location 3 empty, box 4 on the location 4, box 2 on the location 5, box 3 on the location 6 and box 7 on the location 7. We need 6 moves to reach this configuration.