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.

Input

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

Output

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

Scoring

Sample Input 1

20

Sample Output 1

6

Notes

Các số đẹp là: ~2, 3, 5, 7, 12, 20~.