{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $1 \\le T \\le 10^4$\n*   $1 \\le N \\le 10^9$\n*   All input values are integers."},{"iden":"input","content":"The 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$"},{"iden":"sample input 1","content":"4\n3\n16\n1\n55"},{"iden":"sample output 1","content":"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)$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}