AT_tenka1_2017_f ModularPowerEquation!!

输入$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```

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