問題文

はじめに整数 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 に変化させたいです。

これが可能かどうか判定し、可能な場合はこれを達成するために必要なボタンを押す回数の最小値を求めてください。

制約

• 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

出力

答えを T 行にわたって出力してください。

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

入力例 1

3
1 8 13
1 2 3 4 5 6
0 1 3
1 0 1 0 1 0
123456789 634 998244353
1 23 456 7890 123456789 987654321

出力例 1

4
-1
164941630

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 に変化させることはできません。