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


hide comments
samun_49: 2023-08-28 05:39:02

Nice problem. After some brainstorming I able to get AC in 2. Learned something new. Thanks.

sangmai: 2021-05-22 04:40:02

How to prove that the answer is bounded by 2e8?

slimshadynick: 2020-03-10 19:24:33

Anyone Getting nzec in java? My code is running fine locally!

mahdibuet3: 2019-12-07 12:47:56

calculate phi value upto 160126035

mrmajumder: 2019-11-29 16:33:09

How to find the value of totient of a number greater than 10^9?

ajkdrag: 2018-09-04 13:31:26

Getting WA, some test cases please. For n = 1 , case the result should be 1, right?

straw__hat: 2018-05-31 11:44:31

@admin Why I'm getting runtime error for my this sol'n 21755292?

cat_got_bored: 2016-12-03 17:42:56

The solution is straightforward but there are some pitfalls. some tips :
1) Don't do binary search. Sorting will take too much time (TLE).
2)Check for n=1.
3)Use all int arrays (Or will get SEGKILL). inside loops, use long long to avoid overflow.
3)Finally, here n means the the value of totient function, you need to find x. where, ETF(x) = n. Even though, n will be at most 10^8, you need to find x, which can be bigger than 10^8.
4)The maximum x for this problem is 202918035, when n=99683840.
Thanks to problemsetter, Nice problem :)

Chetan: 2015-06-30 13:22:12

Please Help me out here with SPOJ submission 14571312
I've no idea why I keep getting SIGSEGV or SIGKILL here.
I've provided the correct limiting conditions, according to me! :/

[Lakshman]: 2014-01-08 18:52:48

@(Tjandra Satria Gunawan)(曾毅昆)
Can you please tell me why I am getting WA, I think My algorithm is correct.
Please help.


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