問題文

NN 個のマスが円周上に並んだすごろくがあり、マスには、時計回りに 0,1,,N10, 1, …, N - 1 の番号がついています。
ゲーム開始時点では、あなたの駒はマス SS にあり、以下の行動を何回でも行うことができます。

  • 駒があるマスの番号を XX とすると、(X×K)modN(X \times K) \mod N の番号のマスに移動する。

マス GG に到達するための最小の行動回数を求めてください。また、到達できない場合は 1-1 を出力してください。

QQ 個のクエリが与えられます。
ii 個目のクエリでは Ni,Ki,Si,GiN_i, K_i, S_i, G_i が与えられるので、それぞれのクエリについて上記の問題を解いてください。

制約

  • 1Q501 \leq Q \leq 50
  • 0Si,Gi<Ni1090 \leq S_i, G_i < N_i \leq 10^9
  • NiN_i は素数
  • 0Ki1090 \leq K_i \leq 10^9
  • 入力はすべて整数である。

入力

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

Q
N1 K1 S1 G1
N2 K2 S2 G2
...
N_Q K_Q S_Q G_Q

出力

それぞれのクエリに対する答えを改行区切りで出力せよ。

入出力例

入力例1
5
3 5 2 1
11 4 10 5
5 3 4 1
3 10 2 2
2 9 0 1
出力例1
1
-1
2
0
-1

最初のクエリについて、2×52 \times 533 で割ったあまりは 11 なので、11 回の行動でマス 11 にたどり着くことができます。
22 番目のクエリについては、何回行動を行ってもマス 11 にたどり着くことはできません。
33 番目のクエリについては、4×34 \times 355 で割ったあまりは 222×32 \times 355 で割ったあまりは 11 なので、22 回の行動でマス 11 にたどり着くことができます。

Submit


Go (1.21)