Số nguyên tố là số tự nhiên lớn hơn ~1~ và chỉ có đúng hai ước là ~1~ và chính nó. Ví dụ các số tự nhiên ~2, 3, 5, 7, 11, 13, 17, 19, 23, ...~ là các số nguyên tố.

Yêu cầu

Cho số tự nhiên ~n~, hãy tìm số tự nhiên ~p~ thỏa mãn điều kiện: ~p~ là số nguyên tố nhỏ nhất và ~p \ge n~.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất chứa số nguyên dương ~Q~ ~(Q \le 10^6)~ là số bộ test.
• ~Q~ dòng tiếp theo, mỗi dòng chứa một số tự nhiên ~n~ ~(n \le 10^9)~.

Dữ liệu đầu ra

Gồm ~Q~ dòng, mỗi dòng ghi một số nguyên tố tìm được tương ứng với dữ liệu vào.

Ràng buộc dữ liệu

• Có 30% số test ứng với 30% số điểm của bài thỏa mãn: ~Q = 1, n \le 10^3~;
• Có 40% số test khác ứng với 40% số điểm của bài thỏa mãn: ~Q \le 10^2, n \le 10^9~;
• 30% số test còn lại ứng với 30% số điểm của bài thỏa mãn: ~Q \le 10^6, n \le 10^6~.

Ví dụ

Ví dụ 1

INPUT

2
5
8

OUTPUT

5
11

Giải thích:

• Với ~n = 5~, số nguyên tố nhỏ nhất ~p \ge n~ là ~5~;
• Với ~n = 8~, số nguyên tố nhỏ nhất ~p \ge n~ là ~11~.