Last 9 Digits

AtCoder

IDarc172_e

Time2000ms

Memory256MB

Difficulty—

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. ## Constraints * $1 \leq Q \leq 10000$ * $1 \leq X \leq 10^9 - 1$ * $X$ is neither a multiple of $2$ nor a multiple of $5$. * All input values are integers. ## Input 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)$: $Q$ $X_1$ $X_2$ $\vdots$ $X_Q$ [samples]

Samples

Input #1

2
27
311670611

Output #1

3
11

This sample input consists of two test cases.

*   The first case: The remainder of $3^3 = 27$ divided by $10^9$ is $27$, so $n = 3$ satisfies the condition.
*   The second case: The remainder of $11^{11} = 285311670611$ divided by $10^9$ is $311670611$, so $n = 11$ satisfies the condition.

API Response (JSON)

{
  "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## Co...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments