Với số nguyên ~a~, hãy tìm số nguyên tố ~b~ sao cho ~\lvert b - a\rvert~ nhỏ nhất có thể. Nếu có hai số nguyên tố ~b~ cùng đạt ~\lvert b - a\rvert~ nhỏ nhất, đưa ra giá trị ~b~ nhỏ hơn.

Ví dụ:

• Với ~a = 10~, số nguyên tố ~b = 11~ có ~\lvert b - a\rvert = 1~ là giá trị cần tìm.
• Với ~a = 26~, số nguyên tố ~b = 23~ có ~\lvert b - a\rvert = 3~ là giá trị cần tìm. Số nguyên tố ~b = 29~ cũng có ~\lvert b - a\rvert = 3~, nhưng theo quy tắc ta phải đưa ra số nhỏ hơn.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(n \le 10^5)~ là số test.
• ~n~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~a~ ~(2 \le a \le 2 \cdot 10^7)~ ứng với một test.

Output

• Với mỗi test, in ra trên một dòng số nguyên tố ~b~ tìm được.

Sample Input 1

5
2
10
26
100
9999

Sample Output 1

2
11
23
101
10007