{"problem":{"name":"Last 9 Digits","description":{"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$. You will be given $Q$ test cases to solve.","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc172_e"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc172_e","tags":[],"sample_group":[["2\n27\n311670611","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."]],"created_at":"2026-03-03 11:01:14"}}