Problem Statement

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

Output

Print $Q$ lines. The $i$-th line should contain the answer for the $i$-th test case. If no $n$ satisfies the condition, the answer should be $-1$.