{"raw_statement":[{"iden":"problem statement","content":"Process the $Q$ queries below.\n\n*   You are given two integers $A_i$ and $M_i$. Determine whether there exists a positive integer $K_i$ not exceeding $2 × 10^{18}$ such that $A_i^{K_i} ≡ K_i$ $(mod$ $M_i)$, and find one if it exists."},{"iden":"constraints","content":"*   $1 \\leq Q \\leq 100$\n*   $0 \\leq A_i \\leq 10^9(1 \\leq i \\leq Q)$\n*   $1 \\leq M_i \\leq 10^9(1 \\leq i \\leq Q)$"},{"iden":"inputs","content":"Input is given from Standard Input in the following format:\n\n$Q$\n$A_1$ $M_1$\n:\n$A_Q$ $M_Q$"},{"iden":"outputs","content":"In the $i$\\-th line, print $-1$ if there is no integer $K_i$ that satisfies the condition. Otherwise, print an integer $K_i$ not exceeding $2 × 10^{18}$ such that $A_i^{K_i} ≡ K_i$ $(mod$ $M_i)$. If there are multiple solutions, any of them will be accepted."},{"iden":"sample input 1","content":"4\n2 4\n3 8\n9 6\n10 7"},{"iden":"sample output 1","content":"4\n11\n9\n2\n\nIt can be seen that the condition is satisfied: $2^4 = 16 ≡ 4$ $(mod$ $4)$, $3^{11} = 177147 ≡ 11$ $(mod$ $8)$, $9^9 = 387420489 ≡ 9$ $(mod$ $6)$ and $10^2 = 100 ≡ 2$ $(mod$ $7)$."},{"iden":"sample input 2","content":"3\n177 168\n2028 88772\n123456789 987654321"},{"iden":"sample output 2","content":"7953\n234831584\n471523108231963269"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}