题目描述

判断是否存在正整数 $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

输入

2
27
311670611

输出

3
11

说明/提示

限制条件

• $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 翻译