I. Periodic Recurrence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer sequence $$$a_0, a_1, a_2, \dots$$$, in which the first two elements $$$a_0$$$ and $$$a_1$$$ are given, and for $$$i \ge 2$$$, the elements are specified by the recurrent formula $$$a_i = (A\cdot a_{i-1} + B \cdot a_{i-2}) \bmod M$$$.

The period of a sequence is a positive integer $$$T$$$ such that, starting with some $$$i_0$$$, for any $$$i \ge i_0$$$, it holds that $$$a_i = a_{i+T}$$$. Find the smallest period of the given sequence.

Input

The first line contains one integer $$$t$$$ ($$$1\le t \le 100$$$), the number of test cases.

Each test case contains $$$5$$$ integers $$$M$$$, $$$a_0$$$, $$$a_1$$$, $$$A$$$, $$$B$$$ on a single line ($$$2 \le M \le 10^9$$$; $$$0 \le a_0, a_1, A, B \lt M$$$).

Output

For each test case, print a single positive integer, the smallest period of the given sequence.

It can be shown that under the given constraints, the answer always exists and is not greater than $$$10^{18}$$$.

Example
Input
9
3 1 1 1 1
3 0 1 2 2
7 0 0 3 4
10 1 2 3 0
10 1 2 0 3
11 1 1 6 6
12 4 3 2 1
15 3 5 5 2
19 8 2 18 14
Output
8
3
1
4
8
1
8
24
171
Note

Sequences in the first 6 test cases (repeating subsequence is bolded):

  • 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, ....
  • 0, 1, 2, 0, 1, 2, 0, 1, 2, ....
  • 0, 0, 0, ....
  • 1, 2, 6, 8, 4, 2, 6, 8, 4, ....
  • 1, 2, 3, 6, 9, 8, 7, 4, 1, 2, 3, 6, ....
  • 1, 1, 1, ....