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)
hide comments
Akhil Mittal:
20121013 09:20:23
for which test case my code gives wrong answer??..Submission Id:7842540


Ehor Nechiporenko:
20121011 15:46:17
So great task ))


mehmetin:
20121004 02:00:40
Can you say what is the highest value for i (for n <= 100 million)?


Sameer Jain:
20120930 13:22:07
The cube is really fast. My brute force algo takes 50 second on my PC but works in just 12 sec here


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20120928 17:44:18
Well, now this problem running at cube processor, I want to know how fast you are \(^_^)/ 
Added by:  Tjandra Satria Gunawan 
Date:  20120928 
Time limit:  20s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own Problem 