First, we define σ(i) = Sum of all positive divisors of i.

For example: all positive divisors of 60 = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}

So σ(60) = 1 + 2 + 3 + 4 + 5 + 6 + 10 + 12 + 15 + 20 + 30 + 60 = 168

Now for the task: given an integer n find smallest integer i such that σ(i) = n.

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 integer per line.)

Output

For each test case, output the smallest inverse sum of divisors of n. if n doesn't have inverse, output -1.

Example

Input:
5
1
16
40
60
168
Output:
1
-1
27
24
60

Time Limit ≈ 2.5*(My Program Top Speed)

See also: Another problem added by Tjandra Satria Gunawan