AT_pakencamp_2022_day1_n Paken Machine

はじめに整数 $ T $ が与えられます。 $ T $ 個のテストケースについて次の問題を解いてください。 > hiikunZ 君は、誕生日プレゼントとしてパ研マシンをもらいました。 > > パ研マシンには、ディスプレイ、ライト、ボタンが $ 1 $ つずつついています。 > > はじめ、ディスプレイには整数 $ s $ が表示されていて、ライトは赤に点灯しています。 > > hiikunZ 君がボタンを押すたびに、ディスプレイに表示される整数 $ x $ とライトの色は、次の通りに変化します。 > > - ボタンを押す前に、ライトが赤に点灯していた場合、 $ x $ は $ A_r \times x + B_r $ を素数 $ P $ で割ったあまりに変化し、ライトは青に点灯する。 > - ボタンを押す前に、ライトが青に点灯していた場合、 $ x $ は $ A_b \times x + B_b $ を素数 $ P $ で割ったあまりに変化し、ライトは黄に点灯する。 > - ボタンを押す前に、ライトが黄に点灯していた場合、 $ x $ は $ A_y \times x + B_y $ を素数 $ P $ で割ったあまりに変化し、ライトは赤に点灯する。 > > hiikunZ 君はボタンを何回か ( $ 0 $ 回でもよい ) 押すことでディスプレイに表示されている整数を $ t $ に変化させたいです。 > > これが可能かどうか判定し、可能な場合はこれを達成するために必要なボタンを押す回数の最小値を求めてください。

N/A

答えを $ T $ 行にわたって出力してください。 $ i $ $ (1 \leq i \leq T) $ 行目には、 $ i $ 番目のテストケースにおいて、ディスプレイに表示されている整数を $ t $ に変化させるのに必要なボタンを押す回数の最小値を出力してください。ただし、これが不可能な場合は代わりに `-1` と出力してください。

### Sample Explanation 1 $ 1 $ 番目のテストケースにおいて考えます。 ライトの色と、ディスプレイに表示されている整数はボタンを押すたびに次のように変化します。 - 最初、ライトは赤に点灯していて、ディスプレイには整数 $ 1 $ が表示されています。 - $ 1 $ 回目にボタンを押したとき、ディスプレイに表示されている整数は $ 1 \times 1 + 2 = 3 $ を $ 13 $ で割ったあまりである $ 3 $ に変化し、ライトは青に点灯します。 - $ 2 $ 回目にボタンを押したとき、ディスプレイに表示されている整数は $ 3 \times 3 + 4 = 13 $ を $ 13 $ で割ったあまりである $ 0 $ に変化し、ライトは黄に点灯します。 - $ 3 $ 回目にボタンを押したとき、ディスプレイに表示されている整数は $ 5 \times 0 + 6 = 6 $ を $ 13 $ で割ったあまりである $ 6 $ に変化し、ライトは赤に点灯します。 - $ 4 $ 回目にボタンを押したとき、ディスプレイに表示されている整数は $ 1 \times 6 + 2 = 8 $ を $ 13 $ で割ったあまりである $ 8 $ に変化し、ライトは青に点灯します。 つまり、 $ 4 $ 回ボタンを押すことでディスプレイに表示されている整数を $ 8 $ に変化させることができます。 $ 2 $ 番目のテストケースでは、ボタンを何回押してもディスプレイに表示されている整数は $ 0 $ のまま変わらないので、これを $ 1 $ に変化させることはできません。 ### Constraints - $ 1 \leq T \leq 10 $ - $ 2 \leq P \leq 10^9 $ - $ P $ は素数 - $ 0 \leq A_r,A_b,A_y < P $ - $ 0 \leq B_r,B_b,B_y < P $ - $ 0 \leq s,t < P $ - 入力はすべて整数 --- ### 入力 入力は以下の形式で標準入力から与えられます。ここで $ test_i $ は $ i $ 番目のテストケースを意味します。 > $ T $ $ test_1 $ $ test_2 $ $ \vdots $ $ test_T $ 各テストケースは以下の形式で与えられます。 > $ s $ $ t $ $ P $ $ A_r $ $ B_r $ $ A_b $ $ B_b $ $ A_y $ $ B_y $