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 a + b là một số nguyên tố.

Dữ liệu vào: một dòng chứa số nguyên dương a.

Dữ liệu ra: một dòng in ra giá trị b nhỏ nhất thỏa mãn điều kiện.

Ví dụ

Input
5
  

Output
2
  

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

Giới hạn: 70% test với 0 < a < 10^6; 30% test với 10^6 < a < 10^9.