AT_abc270_g [ABC270G] Sequence in mod P

[problemUrl]: https://atcoder.jp/contests/abc270/tasks/abc270_g 次の漸化式で定められる数列 $ 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 $ 個のテストケースが与えられます。

入力は以下の形式で標準入力から与えられる。 > $ 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` を出力せよ。

### 制約 - $ 1\ \leq\ T\ \leq\ 100 $ - $ 2\ \leq\ P\ \leq\ 10^9 $ - $ P $ は素数 - $ 0\leq\ A,B,S,G\