NDIVPHI2 - N DIV PHI_N (Hard)

Given an integer N <= 1025000 find the smallest m <= N such that m/phi(m) is maximum. Where phi is Euler's totient function.

Input

The first line in the input gives the number of test cases T (T <= 200), and then T lines follow each containing an integer N.

Output

Output the smallest required value of m.

Example

Input:
1
10

Output:
6

Added by:SALVO
Date:2010-04-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 ASM64 BASH BF C CSHARP C++ 4.3.2 CPP CPP14 C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCALA SCM guile SCM qobi ST TCL TEXT WHITESPACE
Resource:Frank Rafael Arteaga

hide comments
2011-06-17 22:00:49 mukesh tiwari
Kindly increase the time limit otherwise it would be impossible to get accepted in functional language.
Edit: Thank you Hendrik. Finally accepted in Haskell.

Last edit: 2011-07-17 21:12:39
2010-12-20 10:12:29 germinating
can the time limit be increased to 8secs plzz :) since java is slower
2010-07-25 01:51:40 Anirban Saha
Time Limit is too strict for Java...no Java solution got AC till now
2010-07-16 17:29:15 XeRoN!X
you must have used STL stuff like vectors, i guess 4.3.2 handles it much better than 4.0.0-8. going through gcc online documentation may provide proper reasons.
2010-07-16 17:23:16 biQar
@XeRon!X : thank u very much..!! but i don't know why it happen..!! please know me the reason..!! thanks :)
2010-07-14 10:38:45 XeRoN!X
@disqualified, your friend submitted in c++ 4.3.2 and you are trying in 4.0.0-8.
2010-07-06 15:47:58 biQar
one of my friends got AC on 2010-07-01...but, the same solution got TLE on 2010-07-06...!!! why...????? :o :o :o
2010-05-01 19:32:47 numerix
The problem for Python is, that unavoidable type conversions between str and int are veeeery slow for large integers. All the necessary calculation itself can easily be done in 4 sec. To get a Python solution AC the time limit had to be set very high, but I think that shouldn't be done.
2010-05-01 15:39:31 ~!(*(@*!@^&
8s pls, java is 3 times slower than C++ :)
2010-05-01 12:12:28 SALVO
Please comment if the time limit is too strict for slower languages.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.