{"problem":{"name":"ModularPowerEquation!!","description":{"content":"Process the $Q$ queries below. *   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$ $","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"tenka1_2017_f"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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)$\n\n## Inputs\n\nInput is given from Standard Input in the following format:\n\n$Q$\n$A_1$ $M_1$\n:\n$A_Q$ $M_Q$\n\n## Outputs\n\nIn 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.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"tenka1_2017_f","tags":[],"sample_group":[["4\n2 4\n3 8\n9 6\n10 7","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)$."],["3\n177 168\n2028 88772\n123456789 987654321","7953\n234831584\n471523108231963269"]],"created_at":"2026-03-03 11:01:14"}}