Một số nguyên dương được gọi là "gần nguyên tố" nếu nó có đúng 3 ước số dương hoàn toàn phân biệt (tính cả 1 và chính số đó). Ví dụ 9 là gần nguyên tố vì nó có đúng 3 ước số dương là 1, 3 và 9.

Yêu cầu: Cho số nguyên dương n, tìm k là số gần nguyên tố nhỏ nhất thỏa mãn k >= n

Dữ liệu: nhập từ bàn phím (thiết bị vào chuẩn), một số nguyên dương n <= 10^18

Kết quả: ghi ra màn hình (thiết bị ra chuẩn), một số nguyên duy nhất là số k tim được.

Input:

8

Output:

9