Một số nguyên dương ~x~ được gọi là số đẹp nếu nó đồng thời thỏa mãn hai điều kiện:

• Tổng các chữ số của ~x~ là một số nguyên tố.
• ~x~ chia hết cho tổng các chữ số của nó.

Ví dụ: Các số 12; 20; 21; 30 là số đẹp nhưng các số 6; 8; 11; 19 không phải là số đẹp.

Yêu cầu: Cho số nguyên dương ~N~, hãy viết chương trình cho biết trong đoạn ~[1, N]~ có bao nhiêu số đẹp.

Dữ liệu

Một số nguyên dương ~N~ (~1 \le N \le 10^7~).

Kết quả

Một số nguyên là số lượng số đẹp tìm được.

Ví dụ

Input

20

Output

6

Giải thích: Các số đẹp là: 2, 3, 5, 7, 12, 20.

Giới hạn

• Subtask 1 (80% số điểm): ~N \le 10^4~.
• Subtask 2 (20% số điểm): không ràng buộc gì thêm.