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

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên \(T\) là số lượng test. \((T ≤10000)\).
• T dòng tiếp theo, mỗi dòng chứa một số nguyên \(N\).

Kết quả: Ghi ra gồm nhiều dòng mỗi dòng tương ứng mỗi test.

Ví dụ

Input

3
5
10
17

Output

3
7
13

• Hạn chế thời gian: 5 giây.