問題文

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

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

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

$Q$ 個のクエリが与えられます。
$i$ 個目のクエリでは $N_i, K_i, S_i, G_i$ が与えられるので、それぞれのクエリについて上記の問題を解いてください。

制約

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

入力

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

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

出力

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

入出力例

5
3 5 2 1
11 4 10 5
5 3 4 1
3 10 2 2
2 9 0 1

1
-1
2
0
-1

最初のクエリについて、$2 \times 5$ を $3$ で割ったあまりは $1$ なので、$1$ 回の行動でマス $1$ にたどり着くことができます。
$2$ 番目のクエリについては、何回行動を行ってもマス $1$ にたどり着くことはできません。
$3$ 番目のクエリについては、$4 \times 3$ を $5$ で割ったあまりは $2$、$2 \times 3$ を $5$ で割ったあまりは $1$ なので、$2$ 回の行動でマス $1$ にたどり着くことができます。