Bài 3 : Số nguyên tố (6.0 điểm)

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ó.

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\).

Input

Vào từ tệp văn bản MPRI.INP:

• 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)\).

Output

Ghi ra tệp văn bản MPRI.OUT:

• 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.

Example

2
5
8

5
11

Scoring

• 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\).