In this problem, you have to find the nearest prime number smaller than N.

Input

The first line contains an integer T specifying the number of test cases.

T lines follow, each line contains an integer N.

Output

For each test case, output the result on one line.

Example

Input:
3
5 
10
17

Output:
3
7
13

Constraints

3 <= N <= 2^128
0 < T < 10^5

Information

Input is not randomly chosen.
Prime Again and Previous prime (64 bit edition) are recommended problems before this one.
Time limit is twice the time given by my deterministic_Python_code, but the input file is way too small, so there's still some weakness, and much faster code can get AC... Have fun ;-)

Under construction - please be patient