The problem

Let n be an integer, 100 ≤ n ≤ 10000, find the prime number x, x ≤ n, so that n-p*x is maximum, where p is an integer such that p*x ≤ n < (p+1)*x.

The Input

The first line of the input contains an integer, M, indicating the number of test cases. For each test case, there is a line with a number N, 100 ≤ N ≤ 10000.

The Output

For each test case, the output should consist of one line showing the prime number that verifies the condition above.

Sample Input

5
4399
614
8201
101
7048

Sample Output

2203
311
4111
53
3527