Số nguyên tố

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

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

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.

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