{"problem":{"name":"A^n - 1","description":{"content":"You are given a positive integer $N$ between $1$ and $10^9$, inclusive. Find one pair of positive integers $(A, M)$ satisfying the following conditions. It can be proved that such a pair of integers a","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc191_c"},"statements":[{"statement_type":"Markdown","content":"You are given a positive integer $N$ between $1$ and $10^9$, inclusive.\nFind one pair of positive integers $(A, M)$ satisfying the following conditions. It can be proved that such a pair of integers always exists under the constraints.\n\n*   Both $A$ and $M$ are positive integers between $1$ and $10^{18}$, inclusive.\n*   There exists a positive integer $n$ such that $A^n - 1$ is a multiple of $M$, and the smallest such $n$ is $N$.\n\nYou are given $T$ test cases; solve each of them.\n\n## Constraints\n\n*   $1 \\le T \\le 10^4$\n*   $1 \\le N \\le 10^9$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$\\text{case}_1$\n$\\text{case}_2$\n$\\vdots$\n$\\text{case}_T$\n\nHere, $\\text{case}_i$ denotes the $i$\\-th test case.  \nEach test case is given in the following format:\n\n$N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc191_c","tags":[],"sample_group":[["4\n3\n16\n1\n55","2 7\n11 68\n20250126 1\n33 662\n\nConsider $\\text{case}_1$.\nFor example, if we choose $(A,M)=(2,7)$, then:\n\n*   When $n=1$: $2^1 - 1 = 1$ is not a multiple of $7$.\n*   When $n=2$: $2^2 - 1 = 3$ is not a multiple of $7$.\n*   When $n=3$: $2^3 - 1 = 7$ is a multiple of $7$.\n\nHence, the smallest $n$ for which $A^n - 1$ is a multiple of $M$ is $3$. Therefore, $(A,M)=(2,7)$ is a correct solution. Other valid solutions include $(A,M)=(100,777)$."]],"created_at":"2026-03-03 11:01:13"}}