Description

Recently, Xiao W plans to read a new book that has $p$ pages, with page numbers ranging from $0 \sim p-1$.

Xiao W is busy, so he can read only one page per day. To make things a bit more interesting, he plans to use the linear congruential method he learned at NOI2012 to generate a sequence to decide which page to read each day.

Let $x_i$ denote the $i$-th number generated by this method, i.e., the page Xiao W will read on day $i$. This method requires three parameters $a, b, x_1$, satisfying $0 \leq a, b, x_1 \lt p$, and $a, b, x_1$ are integers. A sequence of integers is generated according to the following formula:

Here, $\bmod$ denotes the remainder operation.

However, this method may cause the same page number to be read on two different days.

Xiao W wants to read page $t$ of this book, so he wants to know the earliest day on which he can read page $t$, or determine that he will never read page $t$.

Input Format

This problem contains multiple test cases in a single test point.

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

Each of the next $T$ lines contains five integers $p, a, b, x_1, t$, representing one test case.

Output Format

For each test case, output one line with a single integer indicating the earliest day on which he reads page $t$. If he will never read page $t$, output $-1$.

3
7 1 1 3 3
7 2 2 2 0
7 2 2 2 1

1 
3 
-1

Hint

Constraints

• $1 \leq T \leq 50$.
• $0 \leq a, b, x_1, t \lt p$, $2 \leq p \leq 10^9$.
• $p$ is a prime.

Translated by ChatGPT 5