Với số nguyên ~a~, hãy tìm số nguyên tố ~b~ sao cho ~|b-a|~ nhỏ nhất có thể. Nếu có hai số nguyên tố ~b~ đều thỏa mãn ~|b-a|~ nhỏ nhất, đưa ra giá trị ~b~ nhỏ hơn.
Ví dụ:

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

Yêu cầu

Tìm giá trị ~b~ thỏa yêu cầu đề bài.

Dữ liệu

Dòng 1 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~ ứng với một test ~(2\le a\le 2\times 10^7)~.

Kết quả

Mỗi dòng ghi một kết quả số ~b~ tìm được ứng với từng ~a~ nhập vào.

Input

5
2
10
26
100
9999

Output

2
11
23
101
10007