SPOJ Problem Set (classical)
12295. Smallest Inverse Euler Totient Function
Problem code: INVPHI

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)
See also: Another problem added by Tjandra Satria Gunawan
