配点 : $1400$ 点

問題文

以下の $Q$ 個のクエリに答えてください。

整数 $A_i,M_i$ が与えられます。$A_i^{K_i} ≡ K_i(mod M_i)$ なる $2 \times 10^{18}$ 以下の正整数 $K_i$ が存在するか判定し、存在するならひとつ求めてください。

制約

• $1 \leq Q \leq 100$
• $0 \leq A_i \leq 10^9(1 \leq i \leq Q)$
• $1 \leq M_i \leq 10^9(1 \leq i \leq Q)$

入力

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

$Q$

$A_1$ $M_1$

:

$A_Q$ $M_Q$

出力

$i$ 行目には、$i$ 個目のクエリに対し、問題文の条件を満たす $K_i$ が存在しないなら、$-1$ を出力せよ。 そうでない場合、$A_i^{K_i} ≡ K_i(mod M_i)$ なる $2 \times 10^{18}$ 以下の正整数 $K_i$ をひとつ出力せよ。考えられるものが複数ある場合、どれを出力してもよい。

4
2 4
3 8
9 6
10 7

4
11
9
2

それぞれ、$2^4 = 16 ≡ 4(mod 4)$、$3^{11} = 177147 ≡ 11(mod 8)$、$9^9 = 387420489 ≡ 9(mod 6)$、$10^2 = 100 ≡ 2(mod 7)$ より、条件を満たします。

3
177 168
2028 88772
123456789 987654321

7953
234831584
471523108231963269