10852 - Less Prime

The problem

令 n 為整數且 100 <= n <= 10000，請找出一質數 x, 且 x <= n，使得 ( n - p*x )的值最大化，其中 p 為整數且 p*x <= n < (p+1)*x。

The Input

輸入的第一列為一整數M，表示測試資料組數，接下來的M列為N，且100<= N <= 10000。

The Output

請依題目的述敘求解，並分別印在每一行。

Sample Input

5
4399
614
8201
101
7048

Sample Output

2203
311
4111
53
3527


原文出處