Interesting Number

Interview

Time limit1sMemory limit512 MB

Summary

Count how many integers from 1 to N are divisible by the sum of their decimal digits.

Level: Easy3 of 10
Topics: Math, Implementation, Brute force, Number theory
Solved: No attempts yet

Problem

Mincheol, a child with a strong interest in numbers, spends his day adding, subtracting, multiplying, and dividing numbers with a pencil in his notebook. He discovered that the number 18 has an interesting property. The sum of its digits, 1 and 8, is 9, and 9 divides 18.

Mincheol found more numbers like 18 that are divisible by the sum of their digits. The numbers 12 and 21 also had this property. Mincheol decided to call a number divisible by the sum of its digits an "interesting number." He looked for larger interesting numbers as well, and found that 1729 is one. 1729 is divisible by 1+7+2+9=19.

Mincheol wants to know how many interesting numbers there are. Given a natural number N, he is curious about the total count of interesting numbers less than or equal to N. However, checking by hand whether every number up to N is interesting takes too long.

You must write a program to help Mincheol. Given a natural number N (N ≥ 1), write a program that outputs the number of interesting numbers less than or equal to N.

Input

The first line gives a single integer N (1 ≤ N ≤ 10,000,000).

Output

Print the number of interesting numbers less than or equal to N as an integer.

Examples2

Example 1
Input
```
9
```
Expected output
```
9
```
Example 2
Input
```
21
```
Expected output
```
14
```