INVPHI  Smallest Inverse Euler Totient Function
This task is the inverse of ETF problem, given an integer n find smallest integer i such that φ(i)=n, where φ denotes Euler's totient function.
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 Euler's Totient Function of n. if n doesn't have inverse, output 1.
Example
Input:
5
10
20
30
40
50 Output:
11
25
31
41
1
Time Limit ≈ 3*(My Program Top Speed)
Added by:  (Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†) 
Date:  20120928 
Time limit:  20s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel Pentium G860 3GHz) 
Languages:  All except: SCM chicken 
Resource:  Own Problem 
hide comments
[Lakshman]:
20140108 18:52:48
@(Tjandra Satria Gunawan)(曾毅昆)


anurag garg:
20131229 04:28:12
@(Tjandra Satria Gunawan)(曾毅昆)


anurag garg:
20131229 04:28:12
Last edit: 20131229 04:28:38 

Sandeep Pathry:
20130712 16:23:38
Finally!!! AC...


Ritam Shukla:
20130119 10:30:39
Though i have a doubt. Why is it that even if i try to run my accepted solution on ideone, it gives a runtime error SIGKILL? Is it that memory limit there is very tight? And is there any special option available there that enables us to use the Cube?


Ritam Shukla:
20130118 21:22:57
One of the finest tasks I've ever done! Great job, Tjandra. Keep it up. :)


Ritam Shukla:
20130112 20:16:19
No, not a super computer. Just a Hyperthreaded Intel Core i73770 4 cores 8 threads with turbo boost 3.9GHz. (I'm using without turbo currently, so I get about 3.5GHz) I think ONE MUST NOT COMPARE IDEONE WITH THE CUBE. What I believe is that ideone is equivalent to the Pyramid cluster of SPOJ, so it is bound to take >15 sec and we know that it cannot be used to time a code which takes more than 15s on Pyramid(correct me if i'm wrong). Though I just checked it out there.


Ritam Shukla:
20130112 10:05:34
@Tjandra, if you see my code, you'll realize that I precompute just once for an input file of any size, and the subsequent processing of the individual test cases (whatever their number may be) won't take more than 12 seconds. Moreover, the initial precomputation takes ~1213 seconds on my PC. Even if there is some error in the logic, with so many people telling that the Cube is so fast, I expected a WA.


Ritam Shukla:
20130112 07:32:15
My brute force approach works on my system in <15 seconds but gives Time Limit Exceeded here on Cube cluster. :(


Snehasish Roy ;):
20121226 17:40:03
@Tjandra: Kindly tell whats the required complexity for the solution to be AC ?
