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

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
def modular_pow(base, exponent, modulus):
 result = 1
 while exponent > 0:
  if(exponent %2 == 1):
   result = (result * base) % modulus
  exponent = exponent//2
  base = (base * base)%modulus
 return result
def passesMillerRabinTest(n, a):
 s = 0
 d = n-1
 while(d%2 == 0):
  s += 1
  d >>= 1
 x = modular_pow(a, d, n)
 if(x == 1 or x == n-1):
  return True
 for ss in range(s - 1):
  x = (x*x)%n
  if(x == 1):
   return False
  if(x == n-1):
   return True
 return False
primeList = (2, 3,5,7,11,13,17,19, 23,29, 31,37)
def isPrime(n):
 for p in primeList:
  if n%p == 0:
   return n == p
 for p in primeList:
  if passesMillerRabinTest(n, p) == False:
   return False
 return True
 
t = int(input())
for tt in range(t):
 n = int(input())
 if(n == 2):
  print(2)
  continue
 if n%2 == 0:
  n -= 1
 while True:
  if(isPrime(n)):
   print(n)
   break
  n -= 2