题目描述

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

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

输入格式

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

$Q$ $A_1$ $M_1$ : $A_Q$ $M_Q$

输出格式

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

题目大意

输入$Q$ $(1\leq Q\leq 100)$组$A,M$ $(0\leq A_i\leq 10^9, 1\leq M_i\leq 10^9(1\leq i\leq Q))$，求任意一个$K$ $(1\leq K\leq 2\times 10^{18})$，使得$A^K\equiv K\ (mod\ M)$

输入格式：

$Q$

$A_1$ $M_1$

$\dots$

$A_Q$ $M_Q$

输出格式：

第$i$行输出第$i$组的$K$值，若没有合法的$K$,则输出-1

4
2 4
3 8
9 6
10 7

4
11
9
2

3
177 168
2028 88772
123456789 987654321

7953
234831584
471523108231963269

提示

制約

• $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)$

Sample Explanation 1

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