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

Dữ liệu:

• Dòng thứ nhất chứa số nguyên dương \(Q(Q \leq 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 < 10^{9})\).

Kết quả:

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

• Có 30% số test ứng với 30% số điểm của bài thỏa mãn: \(Q = \ 1;\ n \leq 10^{3}\).

• Có 40% số test khác ứng với 40% số điểm của bài thỏa mãn: \(Q \leq 10^{2};\ n \leq 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 \leq 10^{6};\ n \leq 10^{6}\).

Ví dụ: