Lostmonkey has gone to great lengths to secure a position as a junior assembly line operator at the fsk company. There are $n$ positions on the assembly line, numbered from $0$ to $n-1$. The initial state is: position $0$ is empty, and for $0 < i < n$, position $i$ contains the box numbered $i$.

Lostmonkey must rearrange these boxes according to the following rules.

The rearrangement rules are described by five numbers $q, p, m, d, s$, where $s$ is the position that must be empty in the final state. To determine the final position of all boxes, first generate a sequence $c$ where $c_0 = 0$ and $c_{i+1} = (c_i \cdot q + p) \bmod m$. Then, starting from the box numbered $1$ up to the box numbered $n-1$, generate the final position for each box in increasing order of their numbers.

Suppose the box numbered $i$ is placed at position $pos_i$. Then: $pos_i = (c_i + d \cdot x_i + y_i) \bmod n$ where $x_i$ and $y_i$ are non-negative integers chosen by you to ensure that the box numbered $i$ is not placed in the same position as any box numbered less than $i$, and $pos_i \neq s$. If there are multiple pairs of $(x_i, y_i)$ that satisfy these requirements, you must choose the one with the smallest $y_i$, and if $y_i$ is the same, the one with the smallest $x_i$.

Following these rules, you can determine the final position of all boxes, which constitutes the target state.

Assuming that in one move you can move a box to an empty position, and the position previously occupied by the moved box becomes empty, what is the minimum number of moves required to transform the state of all boxes from the initial state to the target state?

Input

The first line contains an integer $t$, representing the number of test cases. Each of the following $t$ lines contains six space-separated integers $n, s, q, p, m, d$, as described above.

It is guaranteed that $30\%$ of the data satisfies $n \le 100$. For $100\%$ of the data, $t \le 20$, $n \le 100000$, and $s < n$. All other numbers are positive integers not exceeding $100000$.

Output

The output contains $t$ lines. The $i$-th line should contain the minimum number of moves required to transform the boxes from the initial state to the target state for the $i$-th problem.

Examples

Input 1

1
8 3 5 2 7 4

Output 1

6

Note

In the target state, boxes numbered $1$ through $7$ are placed at positions $2, 5, 6, 4, 1, 0, 7$ respectively. During the calculation, the values of the expressions may exceed the range of a standard integer.