Little W likes reading, especially Jean-Christophe. Recently, Little W is preparing to read a new book, which has a total of $p$ pages, with page numbers ranging from $0$ to $p-1$.
Little W is very busy, so he can only read one page per day. To make things interesting, he plans to use the linear congruential generator he learned at NOI2012 to generate a sequence to decide which page to read each day.
We use $X_i$ to represent the $i$-th number generated by this method, which is the page Little W will read on the $i$-th day. This method requires setting three parameters $a, b, X_1$, satisfying $0 \le a, b, X_1 \le p-1$, where $a, b, X_1$ are all integers. A series of integers is generated according to the following formula: $$X_{i+1} = (aX_i + b) \pmod p$$ where $\pmod p$ denotes the remainder of the preceding number divided by $p$.
It can be observed that the next number in this sequence is always generated from the previous one, and each term is within the range $0 \dots p-1$, which is a valid page number. It should also be noted that this method may result in the same page being read on two different days.
Little W is very eager to read page $t$ of this book. Therefore, he wants to know, for a given set of $a, b, X_1$, if the linear congruential generator is used to generate the page to read each day, on which day will he first read page $t$, or indicate that he will never read page $t$.
Input
The input contains multiple test cases. The first line contains a positive integer $T$, representing the number of test cases. Following this are $T$ lines, each containing five integers $p, a, b, X_1, t$, representing a test case. It is guaranteed that $X_1$ and $t$ are valid page numbers.
Output
There are $T$ lines in total, each containing an integer representing the day he first reads page $t$. If he will never read page $t$, output -1.
Examples
Input 1
3 7 1 1 3 3 7 2 2 2 0 7 2 2 2 1
Output 1
1 3 -1
Note
For the first test case, the generated sequence is: $3, 4, 5, 6, 0 \dots$ For the second and third test cases, the generated sequence is: $2, 6, 0, 2 \dots$
Constraints
| Test Case ID | $a$ | $b$ | $p$ |
|---|---|---|---|
| 1 | $0 \le a \le p-1$ | $0 \le b \le p-1$ | $2 \le p \le 100$ |
| 2 | $a=1$ | $0 \le b \le p-1$ | $2 \le p \le 10^9$ |
| 3 | $a=1$ | $0 \le b \le p-1$ | $2 \le p \le 10^9$ |
| 4 | $a=1$ | $0 \le b \le p-1$ | $2 \le p \le 10^9$ |
| 5 | $a=1$ | $0 \le b \le p-1$ | $2 \le p \le 10^9$ |
| 6 | $0 \le a \le p-1$ | $b=0$ | $2 \le p \le 10^9$ |
| 7 | $0 \le a \le p-1$ | $b=0$ | $2 \le p \le 10^9$ |
| 8 | $0 \le a \le p-1$ | $b=0$ | $2 \le p \le 10^9$ |
| 9 | $0 \le a \le p-1$ | $0 \le b \le p-1$ | $2 \le p \le 10^9$ |
| 10 | $0 \le a \le p-1$ | $0 \le b \le p-1$ | $2 \le p \le 10^9$ |
For 100% of the test data: $p$ is guaranteed to be a prime number, $T \le 50$.