Cho \(1\) số nguyên dương \(n\) hãy tìm số nguyên tố tiếp theo.

Input

• Dòng đầu tiên là \(1\) số nguyên \(t\) là số lượng câu hỏi
• \(t\) dòng tiếp theo chứa \(t\) số nguyên \(n\)

Output

• Với mỗi câu hỏi, in ra số nguyên tố tiếp theo sau \(n\)

Constraints

• \(1 \le t \le 20\)
• \(1 \le n \le 10^{12}\)

Example

5
1
2
3
42
1337

2
3
5
43
1361