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 integer 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
samun_49:
20230828 05:39:02
Nice problem. After some brainstorming I able to get AC in 2. Learned something new. Thanks. 

sangmai:
20210522 04:40:02
How to prove that the answer is bounded by 2e8? 

slimshadynick:
20200310 19:24:33
Anyone Getting nzec in java? My code is running fine locally! 

mahdibuet3:
20191207 12:47:56
calculate phi value upto 160126035 

mrmajumder:
20191129 16:33:09
How to find the value of totient of a number greater than 10^9? 

ajkdrag:
20180904 13:31:26
Getting WA, some test cases please. For n = 1 , case the result should be 1, right?


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)(曾毅昆)

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 