INVDIV - Smallest Inverse Sum of Divisors

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


Added by:Tjandra Satria Gunawan
Date:2012-09-29
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem

hide comments
2012-10-01 18:34:31 Damian Straszak
I think this one is easier ;) But maybe my methods are so primitive you didn't expect it ;D

Last edit: 2012-10-01 18:35:37
2012-09-29 10:24:21 (Tjandra Satria Gunawan)(曾毅昆)
I bet this problem is harder than before ;-)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.