Câu 2 đề thi HSG 11 tỉnh Bắc Giang năm 2022-2023)

An và Nhiên đang xem một bộ phim nói về cuộc đời của nhà toán học: Alan Turing - người đã chế tác thành công máy giải mã. 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 An biế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ó. Ngồi cạnh cây toán của lớp An muốn mở rộng khái niệm này và hỏi Nhiên: "Những số có 3 ước dương khác nhau thì như thế nào" - Nhiên nói "các số này là bình phương của số nguyên tố, những số đầu tiên là 4, 9, 25, 49, 121, 169,..." mình gọi là số gần nguyên tố.

Cho số nguyên dương ~n~.

Yêu cầu:

Hãy tìm số gần nguyên tố nhỏ nhất lớn hơn hoặc bằng ~n~.

Input:

Một dòng ghi số nguyên dương ~n~ (~n≤~10^18).

Output:

Ghi ra một số nguyên dương ~m~ duy nhất là số gần nguyên tố nhỏ nhất lớn hơn hoặc bằng ~n~

Ví dụ:

input

21

output

25