spoj#INVDIV. Smallest Inverse Sum of Divisors
Smallest Inverse Sum of Divisors
First, we define σ(i) = Sum of all positive divisors of i.
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 ineger per line)
Output
For each test case, output 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)