Tìm số nguyên tố gần nhất nhỏ hơn ~N~ ~\left(3 \leq N \leq 2^{32}\right)~.

Input

Dòng đầu tiên chứa số nguyên ~T~ là số lượng test ~\left(T \leq 10000\right)~

~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~N~.

Output

Với mỗi test, in kết quả trên một dòng.

Sample Input

3
5
10
17

Sample Output

3
7
13