Just Too Lucky

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$.

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

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