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

见题面

见题面