描述

欧拉函数 φ(n) 定义为不超过正整数 n 并且与 n 互素的整数的数目。
可以证明，
φ(n) = n ∗ ∏ ( (pi-1)/pi )
其中pi为n的全部素因子。
已知 y，求最小的自然数 x 使得 φ(x) = y.
多组询问。

格式

输入格式

第一行，一个整数 T，表示多少组询问。
接下来 T 行，每行一个整数 yi。保证有解。

输出格式

输出 T 行，每行一个整数，依次表示每次询问的答案。

样例1

样例输入1

4
10
2
104
8800440

样例输出1

11
3
159
8809079

限制

30% 的数据：1 <= y <= 10^6.
60% 的数据：1 <= y <= 10^9.
100% 的数据：1 <= y <= 10^12，1 <= T <= 2.

提示

前 20 个正整数的欧拉函数值依次是 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8.

来源

BJOI 2014 Day 1