← 返回题目列表

AtCoder · arc172_e

E. 最后 9 位数字

中文机器翻译题面 查看原题

分数: 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 满足条件。