Description

Finding a job is not easy. Lostmonkey finally managed to get an entry-level assembly line operator position at fsk. There are $n$ positions on the line, numbered from $0$ to $n - 1$. Initially, position $0$ is empty, and each other position $i$ holds a box numbered $i$. Lostmonkey needs to rearrange these boxes according to the following rules.

The rules are determined by five numbers, $q, p, m, d, s$, where $s$ is the final position of the empty slot.

First, generate a sequence $c$ with $c_0=0$, and $c_{i+1}=(c_i\times q+p)\bmod m$.

Next, starting from the first box, generate the final position $pos_i$ for each box in order: $pos_i=(c_i+d\times x_i+y_i)\bmod n$, where $x_i, y_i$ are non-negative integers chosen by you so that the $i$-th box does not share the same position as any previous box, and $pos_i$ must not be $s$.

If there are multiple sequences $x, y$ that satisfy the requirements, you must choose the one with the lexicographically smallest $y$. If $y$ is the same, choose the lexicographically smallest $x$. In this way, you obtain the final positions for all boxes. Each move allows you to move any box into the empty slot; after moving, the original position of that box becomes the empty slot.

Find the minimum number of moves required to move all boxes to their final positions.

Input Format

The first line contains an integer $t$, the number of test cases.

Then follow $t$ lines. Each line contains six numbers, $n, s, q, p, m, d$, as described above.

Output Format

For each test case, output one number on a single line, the minimum number of moves.

1
8 3 5 2 7 4

6

Hint

[Sample Explanation]

The final positions of boxes $1$ through $7$ are: $[2, 5, 6, 4, 1, 0, 7]$.

Constraints

• For $30\%$ of the testdata, $n \le 100$.
• For $100\%$ of the testdata, $1 \le t \le 20$, $1 \le n \le 100000$, $0 \le s < n$.
• All other numbers are positive integers not exceeding $100000$.

Additional Hint

The computation may exceed the integer range.

Translated by ChatGPT 5