Hai số tự nhiên M và N được gọi là 2 số nguyên tố cùng nhau nếu ước chung lớn nhất của chúng bằng 1. Khi đó ta cũng nói M nguyên tố cùng nhau với N hoặc N nguyên tố cùng nhau với M.

Yêu cầu: Cho trước số tự nhiên X (X >1). Hãy tìm số tự nhiên K nhỏ nhất (K>1) đồng thời nguyên tố cùng nhau với tất cả các số tự nhiên từ 1 đến X.

Ví dụ: Với X = 6 thì số K cần tìm là 7.

Dữ liệu vào: Đọc từ file văn bản NTCN.INP chứa một số tự nhiên x (1 < x < 10¹²).

Dữ liệu ra: Ghi ra file văn bản NTCN.OUT số tự nhiên K cần tìm.

Ví dụ: