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 duy nhất là số lượng số đẹp tìm được.

Example

20

6

Scoring

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