[ARC172E] Last 9 Digits

有 $Q$ 次询问，每次给出一个数 $X$，求最小的 $n$ 使得 $n^n\equiv X\pmod{10^9}$。 保证 $X$ 既不是 $2$ 的倍数也不是 $5$ 的倍数。 若无解则输出 $-1$。

[problemUrl]: https://atcoder.jp/contests/arc172/tasks/arc172_e $ 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 $ とします。

2
27
311670611

3
11

### 制約 - $ 1\ \leq\ Q\ \leq\ 10000 $ - $ 1\ \leq\ X\ \leq\ 10^9\ -\ 1 $ - $ X $ は $ 2 $ の倍数でも $ 5 $ の倍数でもない - 入力はすべて整数 ### Sample Explanation 1 この入力例は $ 2 $ 個のテストケースからなります。 - $ 1 $ 個目：$ 3^3\ =\ 27 $ を $ 10^9 $ で割った余りは $ 27 $ なので、$ n\ =\ 3 $ で条件を満たします。 - $ 2 $ 個目：$ 11^{11}\ =\ 285311670611 $ を $ 10^9 $ で割った余りは $ 311670611 $ なので、$ n\ =\ 11 $ で条件を満たします。