Just Too Lucky

Time limit3sMemory limit256 MB

Summary

Count integers from 1 to n (up to 10^12) whose value is divisible by its own digit sum, requiring digit-DP over fixed digit-sum targets.

Level: Hard8 of 10
Topics: Dynamic programming, Combinatorics, Math
Solved: No attempts yet

Problem

Ever since public transit was invented, passengers have looked for lucky ticket numbers. There are many definitions of a lucky ticket: sometimes a ticket is lucky when the sum of the first half of its digits equals the sum of the second half, sometimes the products of the digits are compared, and so on.

In the city of St Andrewburg the tickets are numbered with the integers from $1$ to $n$ . Bill calls a ticket lucky when its number is divisible by the sum of its digits. Help Bill count how many lucky tickets there are.

For example, ticket $102$ is lucky, because its digit sum is $1 + 0 + 2 = 3$ and $102$ is divisible by $3$ .

Input

The only line contains a single integer $n$ ( $1 \le n \le 10^{12}$ ).

Output

Print a single integer — the number of lucky tickets among $1, 2, \dots, n$ .

Examples6

Example 1
Input
```
1
```
Expected output
```
1
```
Example 2
Input
```
9
```
Expected output
```
9
```
Example 3
Input
```
10
```
Expected output
```
10
```
Example 4
Input
```
13
```
Expected output
```
11
```
Example 5
Input
```
100
```
Expected output
```
33
```
Example 6
Input
```
1000
```
Expected output
```
213
```