AT_tenka1_2017_f ModularPowerEquation!!

[problemUrl]: https://atcoder.jp/contests/tenka1-2017/tasks/tenka1_2017_f 以下の $ 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 $ をひとつ出力せよ。考えられるものが複数ある場合、どれを出力してもよい。

### 制約 - $ 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) $ より、条件を満たします。