G. Short Tasktime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputLet us denote by d(n) the sum of all divisors of the number n, i.e. d(n) = \sum\limits_{k | n} k.For example, d(1) = 1, d(4) = 1+2+4=7, d(6) = 1+2+3+6=12.For a given number c, find the minimum n such that d(n) = c.InputThe first line contains one integer t (1 \le t \le 10^4). Then t test cases follow.Each test case is characterized by one integer c (1 \le c \le 10^7).OutputFor each test case, output:   "-1" if there is no such n that d(n) = c;  n, otherwise. ExampleInput
12
1
2
3
4
5
6
7
8
9
10
39
691
Output
1
-1
2
3
-1
5
4
7
-1
-1
18
-1

12
1
2
3
4
5
6
7
8
9
10
39
691

1 -1 2 3 -1 5 4 7 -1 -1 18 -1 
['brute force', 'dp', 'math', 'number theory', '*1700']