AT_arc172_e [ARC172E] Last 9 Digits

判断是否存在正整数 $n$，使得 $n^n$ 除以 $10^9$ 的余数等于 $X$，如果存在，求出最小的 $n$。对于给定的 $Q$ 个测试用例，请分别输出答案。

输入以如下格式从标准输入读入。对于第 $i$ 个测试用例 $(1 \leq i \leq Q)$，$X$ 的值为 $X_i$。 > $Q$ > $X_1$ > $X_2$ > $\vdots$ > $X_Q$

请输出 $Q$ 行，第 $i$ 行输出第 $i$ 个测试用例的答案。如果不存在满足条件的 $n$，输出 $-1$。

### 限制条件 - $1 \leq Q \leq 10000$ - $1 \leq X \leq 10^9 - 1$ - $X$ 不是 $2$ 的倍数，也不是 $5$ 的倍数 - 所有输入均为整数 ### 样例解释 1 本输入样例包含 $2$ 个测试用例。 - 第 $1$ 个：$3^3 = 27$，$27$ 除以 $10^9$ 的余数是 $27$，所以 $n = 3$ 满足条件。 - 第 $2$ 个：$11^{11} = 285311670611$，$285311670611$ 除以 $10^9$ 的余数是 $311670611$，所以 $n = 11$ 满足条件。 由 ChatGPT 4.1 翻译