分数: 800 点
问题陈述
判断是否存在正整数 n 这样剩余的 n^n 除以 10^9 is X。如果存在,找到最小的这样的 n.
你将得到 Q 测试用例解决。
约束
- 1 \leq Q \leq 10000
- 1 \leq X \leq 10^9 - 1
- X 既不是以下的倍数 2 也不是的倍数 5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出,其中 X_i 的值 X 在 i- 第一个测试用例 (1 \leq i \leq Q):
Q X_1 X_2 \vdots X_Q
输出
打印 Q 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。如果没有 n 满足条件,答案应该是 -1.
示例输入 1
2 27 311670611
示例输出 1
3 11
此示例输入由两个测试用例组成。
- 第一种情况:剩余的 3^3 = 27 除以 10^9 is 27,所以 n = 3 满足条件。
- 第二种情况:剩余的 11^{11} = 285311670611 除以 10^9 is 311670611,所以 n = 11 满足条件。