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. 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. 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