Hai số nguyên dương và được gọi là cặp số "hàng xóm" nếu chúng thỏa mãn trong điều kiện sau:
Trong biểu diễn thập phân, và có cùng độ dài và khác nhau chính xác một chữ số. (Ví dụ là cặp số "hàng xóm")
Nếu ta thêm một chữ số vào bên trái của ặ thì ta sẽ thu được ặ (Ví dụ là cặp số "hàng xóm")
Bây giờ, ta gọi số nguyên tố là "bà con" với số nếu tồn tại một chuỗi số thỏa mãn điều kiện sau:
(Trong đó là tập hợp các số nguyên tố.)
Nói cách khác, tồn tại một dãy chuyển hóa thành mà tất cả các số trong dãy là số nguyên tố, hai số kề nhau phải là "hàng xóm" và tất cả các số trong dãy không quá .
Ví dụ, là số "bà con" với vì ta có dãy sau: .
Cho số nguyên dương và gọi là tổng của tất cả các số nguyên tố không quá và không "bà con" với số .
Yêu cầu: Nhập số nguyên dương . In ra tương ứng.
Input:
- Một dòng duy nhất chứa số nguyên dương
Output:
Ví dụ :
Input:
Output:
Giải thích: Từ đến chỉ có duy nhất số là số nguyên tố không "bà con" với số nên đáp án là
Subtask:
Comments