Cho một số nguyên dương ~n~, nhiệm vụ của bạn là tìm số nguyên tố đầu tiên lớn hơn ~n~.

Đầu vào:

Dòng đầu tiên chứa số nguyên ~t~: số lượng test.

Tiếp theo là ~t~ dòng, mỗi dòng chứa một số nguyên dương ~n~.

Đầu ra:

Với mỗi test, in ra số nguyên tố nhỏ nhất lớn hơn ~n~.

Ràng buộc:

~1 \le t \le 20~

~1 \le n \le 10^{12}~

Ví dụ :

Input:

5
1
2
3
42
1337

Output:

2
3
5
43
1361