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)

See also: Another problem added by Tjandra Satria Gunawan


Added by:Tjandra Satria Gunawan
Date:2012-09-28
Time limit:20s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem

hide comments
2012-10-13 09:20:23 Akhil Mittal
for which test case my code gives wrong answer??..Submission Id:-7842540

Got AC..:)

Last edit: 2012-10-13 09:37:07
2012-10-11 15:46:17 Ehor Nechiporenko
So great task ))

Ans: Thanks :)

Last edit: 2012-10-11 16:16:42
2012-10-04 02:00:40 mehmetin
Can you say what is the highest value for i (for n <= 100 million)?

Ans: highest value: i=202918035, when n=99683840

Last edit: 2012-10-04 11:38:37
2012-09-30 13:22:07 Sameer Jain
The cube is really fast. My brute force algo takes 50 second on my PC but works in just 12 sec here

Ans: yes, the cube is faster than my PC too, my semi-brute-force algo is 16s on my PC, and 6.83s here on cube processor. Congratulations, now you may try the harder version of this problem type: Smallest Inverse Sum of Divisors :-)

Last edit: 2012-09-30 15:00:43
2012-09-28 17:44:18 (Tjandra Satria Gunawan)(曾毅昆)
Well, now this problem running at cube processor, I want to know how fast you are \(^_^)/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.