Witua and Math

All submissions for this problem are available.
Witua is a little student from the University of Lviv. He enjoys studying math. Witua knows a lot of famous mathematicians like Eratosthenes, Pythagoras, Fermat, Diophantus, Furko, Gauss and so on. However, his favorite one is Euler. The only thing Witua likes more than Euler is Euler’s totient function φ. He is exploring the nature of this function. One of the steps of his work is finding φ(i)/i for all 2≤i≤N. He doesn’t need to know every such value, but Witua wonders for what value i, is φ(i)/i the maximum he can get? Help little student to find such i that φ(i)/i is maximum among all the 2≤i≤N.
Input
The first line contains single integer T  the number of test cases. Each of the next T lines contains a single integer N.
Output
For every test case output i such that φ(i)/i is maximum among all i (2≤i≤N) in a separate line.
Constrains
T (1≤T≤500 )
N(2≤N≤10^18)
Example
Input: 3 2 3 4 Output: 2 3 3 Explanation φ(2)/2=1/2 φ(3)/3=2/3 φ(4)/4=2/4
Author:  rubanenko 
Tester:  pieguy 
Editorial  http://discuss.codechef.com/problems/WITMATH 
Tags  Rubanenko, may13, millerrabin, primenumbers, simple 
Date Added:  2082012 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 