Bộ phim mà Dũng và Mai xem nói về cuộc đời nhà toán học Alan Turing - người đã chế tác thành công máy giải mã mà nhờ đó quân đội Anh đã phát hiện sớm nhiều chiến dịch quân sự của phát xít Đức trong chiến tranh thế giới lần 2 (1939-1945). Một trong những nền tảng quan trọng của việc giải mã là kiểm tra xem một số nguyên có phải là số nguyên tố. Tất nhiên Mai biết số nguyên tố là các số nguyên lớn hơn 1 và chỉ có hai ước dương (1 và chính nó). Ngồi cạnh “cây toán” của lớp Mai muốn mở rộng khái niệm này và hỏi Dũng: “Những số chỉ có 3 ước dương khác nhau thì như thế nào?”. “Thật tuyệt!” - Dũng nói “các số này là bình phương của một số nguyên tố, những số đầu tiên là 4, 9, 25, 49,121,... Tớ gọi đó là số gần nguyên tố!”.

Sẵn tờ vé xem phim có dãy số là sery của vé (có thể coi như là một số nguyên dương m) Mai đề nghị Dũng tìm một số “gần nguyên tố” nhỏ nhất lớn hơn hoặc bằng n. Tất nhiên cô bạn gái của chúng ta nhận được câu trả lời “ngay và luôn!” từ cậu bạn thân của mình. Còn bạn - những lập trình viên tương lai hiển nhiên không cần phải tính. Chúng ta chỉ cần viết một chương trình và máy tính tự nó cho câu trả lời!

Yêu cầu: Cho biết số nguyên dương n. Hãy tìm số gần nguyên tố nhỏ nhất lớn hơn hoặc bằng n .

Dữ liệu vào: Nhập từ bàn phím duy nhất số nguyên dương n (n<=10¹⁸)

Dữ liệu ra: In ra màn hình số nguyên A là số gần nguyên tố nhỏ nhất lớn hơn hoặc bằng n.

Ví dụ:

Ghi chú: Bài được chấm trên 8 test, mỗi test 0.25 điểm. Trong đó:

• 4 test có giá trị n<=100
• 2 test tiếp theo có n<=10⁶
• 2 test còn lại không có ràng buộc bổ sung.