NDIVPHI2 - N DIV PHI_N (Hard)

no tags 

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

hide comments
David: 2021-08-31 22:07:07

As noted in other comments, Java I/O is slow. No existing Java solutions. Java will need more time.

Sayak Haldar: 2015-01-27 19:51:11

precomputation+binary search got ac with c++

Last edit: 2015-01-28 20:03:54
Deepanker Aggarwal: 2014-03-09 11:38:06

Please increase time limit for JAVA

(Tjandra Satria Gunawan)(曾毅昆): 2012-10-06 18:03:38

Finally AC, really hard problem :-)

Pankaj Jindal: 2012-06-25 12:18:16

I am getting WA, can anyone paste some large test cases or if there is any corner case..
Thanks!!!

Edit: Finally AC'ed

Last edit: 2012-09-27 20:15:21
Vinay Saini: 2011-09-02 02:01:46

My c++ solution gives TLE while applying same concept, with haskell solution i got AC !!

Michael T: 2011-07-04 17:43:46

Maybe haskell's gmp saves here.

It definitely does. :)

Last edit: 2011-07-12 11:21:33
hendrik: 2011-07-04 15:46:05

numerix: I use standard functions: ByteString.readInteger to convert and print for output. Nothing home made.

Last edit: 2011-07-04 15:46:51
numerix: 2011-07-04 11:48:53

hendrik: But only with efficient I/O handling, I guess.

hendrik: 2011-07-03 22:14:03

mukesh: never say never. For this one HASK can make it.


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