配点 : $600$ 点

問題文

次の漸化式で定められる数列 $X=(X_0,X_1,\ldots)$ があります。

$X_i = \left\{ \begin{array}{ll} S & (i = 0)\\ (A X_{i-1}+B) \bmod P & (i \geq 1) \end{array} \right.$

$X_i=G$ となる $i$ が存在するか判定し、存在するならばそのような最小の $i$ を求めてください。 ここで、$x \bmod y$ は、$x$ を $y$ で割ったあまり(最小非負剰余)を表すものとします。

$1$ ファイルにつき $T$ 個のテストケースが与えられます。

制約

• $1 \leq T \leq 100$
• $2 \leq P \leq 10^9$
• $P$ は素数
• $0\leq A,B,S,G < P$
• 入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

$T$

$\mathrm{case}_1$

$\mathrm{case}_2$

$\vdots$

$\mathrm{case}_T$

各テストケースは以下の形式で与えられる。

$P$ $A$ $B$ $S$ $G$

出力

$T$ 行出力せよ。 $t$ 行目には、$\mathrm{case}_t$ について、$X_i=G$ となる最小の $i$ を出力せよ。そのような $i$ が存在しないならかわりに -1 を出力せよ。

3
5 2 1 1 0
5 2 2 3 0
11 1 1 0 10

3
-1
10

$1$ 番目のケースについて、$X=(1,3,2,0,\ldots)$ であることから、$X_i=0$ となる最小の $i$ は $3$ です。 $2$ 番目のケースについて、$X=(3,3,3,3,\ldots)$ であることから、$X_i=0$ となる $i$ は存在しません。