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
straw__hat:
20180531 11:44:31
@admin Why I'm getting runtime error for my this sol'n 21755292? 

cat_got_bored:
20161203 17:42:56
The solution is straightforward but there are some pitfalls. some tips :


Chetan:
20150630 13:22:12
Please Help me out here with SPOJ submission 14571312


[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.

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 