INVDIV  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)
hide comments
Scape:
20150725 20:09:22
Nice problem, a naive algorithm (or optimized naive algorithm) will simply not pass. You need something faster than N * log N. 

[Lakshman]:
20150725 11:12:08
@Tjandra Satria Gunawan Can you please check my last submission, I have checked several inputs but don't understand for what kind of input I am getting WA.


[Lakshman]:
20140111 19:58:26
Last edit: 20150725 11:10:32 

abdou_93:
20131119 14:31:01
@Tjandra..can you tell me if my alg is efficient or not .. id(10504008)..thanks alot :D 

Sandeep Pathry:
20130714 13:16:59
@tjandra.. Plz see my code... It takes 11.11s on spoj cube... Chcked it on INVPHI...


Snehasish Roy ;):
20121229 10:50:38
@Tjandra: Kindly see submission id: 8370397 and suggest whether my method of filling divsum[] is inefficient or is there another problem with my code !!


Ashish Lavania:
20121221 16:44:03
Same problem as INVPHI.


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20121022 07:48:30
AC % Ratio = 7,14%, definitely this is hard problem, but I agree with you too Damian Straszak if you already know the method this is easier than before because limit of seaching is lower. 

Damian Straszak:
20121001 18:34:31
I think this one is easier ;) But maybe my methods are so primitive you didn't expect it ;D Last edit: 20121001 18:35:37 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20120929 10:24:21
I bet this problem is harder than before ;) 
Added by:  Tjandra Satria Gunawan 
Date:  20120929 
Time limit:  10s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own Problem 