Yêu cầu

Nhập từ bàn phím một số nguyên dương a. Hãy tìm và in ra số nguyên dương b nhỏ nhất sao cho tổng a + b là một số nguyên tố.

Ví dụ

Sample input

5

Sample output

2

Giải thích: Số 2 là số nguyên dương nhỏ nhất thoả mãn 5 + 2 = 7 là một số nguyên tố.

Giới hạn:

• 70% test ứng với 0 ≤ a ≤ 10^6.

• 30% test ứng với 10^6 ≤ a ≤ 10^9.

Hai số tự nhiên được gọi là Nguyên tố tương đương nếu chúng có chung các ước số là số nguyên tố. Ví dụ các số 75 và 15 là nguyên tố tương đương vì cùng có các ước nguyên tố là 3 và 5. Cho trước hai số tự nhiên N, M. Hãy viết chương trình kiểm tra xem các số này có là nguyên tố tương đương với nhau hay không.?

In ra YES nếu thõa mãn và NO khi không thõa.

Ví dụ

Sample Input

75 15

Sample Output

YES

Số tự nhiên y được gọi là một ước thực sự của số tự nhiên x nếu x chia hết cho y và x > y.

Yêu cầu

Nhập vào từ bàn phím một số nguyên dương x (với x > 1), hãy tìm và in ra màn hình số là ước thực sự lớn nhất của số x.

Input: Một số nguyên dương x.

Output: Ghi ra số nguyên m thỏa mãn yêu cầu của đề bài.

Scoring:

• Có 70% test tương ứng với ~x ≤ 10^6~.
• Có 20% test tương ứng với ~x ≤ 10^8~.
• Có 10% test tương ứng với ~x ≤ 10^10~.

Ví dụ

Sample input

10

Sample output

5