{"raw_statement":[{"iden":"problem statement","content":"Determine whether there is a positive integer $n$ such that the remainder of $n^n$ divided by $10^9$ is $X$. If it exists, find the smallest such $n$.\nYou will be given $Q$ test cases to solve."},{"iden":"constraints","content":"*   $1 \\leq Q \\leq 10000$\n*   $1 \\leq X \\leq 10^9 - 1$\n*   $X$ is neither a multiple of $2$ nor a multiple of $5$.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format, where $X_i$ is the value of $X$ in the $i$\\-th test case $(1 \\leq i \\leq Q)$:\n\n$Q$\n$X_1$\n$X_2$\n$\\vdots$\n$X_Q$"},{"iden":"sample input 1","content":"2\n27\n311670611"},{"iden":"sample output 1","content":"3\n11\n\nThis sample input consists of two test cases.\n\n*   The first case: The remainder of $3^3 = 27$ divided by $10^9$ is $27$, so $n = 3$ satisfies the condition.\n*   The second case: The remainder of $11^{11} = 285311670611$ divided by $10^9$ is $311670611$, so $n = 11$ satisfies the condition."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}