This task is the inverse of ETF problem, given an integer n find smallest integer i such that φ(i)=n, where φ denotes Euler's totient function.

Input

The first line is an integer T(1 ≤ T ≤ 100,000), denoting the number of test cases. Then, T test cases follow.

For each test case, there is an integer n(1 ≤ n ≤ 100,000,000) written in one line. (one ineger per line)

Output

For each test case, output Smallest Inverse Euler's Totient Function of n. if n doesn't have inverse, output -1.

Example

Input:
5
10
20
30
40
50
Output:
11
25
31
41
-1

Time Limit ≈ 3*(My Program Top Speed)

See also: Another problem added by Tjandra Satria Gunawan