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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '# cook your dish here\ndef modular_pow(base, exponent, modulus):\n result = 1\n while exponent > 0:\n  if(exponent %2 == 1):\n   result = (result * base) % modulus\n  exponent = exponent//2\n  base = (base * base)%modulus\n return result\ndef passesMillerRabinTest(n, a):\n s = 0\n d = n-1\n while(d%2 == 0):\n  s += 1\n  d >>= 1\n x = modular_pow(a, d, n)\n if(x == 1 or x == n-1):\n  return True\n for ss in range(s - 1):\n  x = (x*x)%n\n  if(x == 1):\n   return False\n  if(x == n-1):\n   return True\n return False\nprimeList = (2, 3,5,7,11,13,17,19, 23,29, 31,37)\ndef isPrime(n):\n for p in primeList:\n  if n%p == 0:\n   return n == p\n for p in primeList:\n  if passesMillerRabinTest(n, p) == False:\n   return False\n return True\n \nt = int(input())\nfor tt in range(t):\n n = int(input())\n if(n == 2):\n  print(2)\n  continue\n if n%2 == 0:\n  n -= 1\n while True:\n  if(isPrime(n)):\n   print(n)\n   break\n  n -= 2\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13421