A. Number Reduction
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver is given a positive integer $$$k$$$ ($$$1 \le k \le 10^{18}$$$) written in base $$$10$$$. Then, he repeatedly performs the following operation:

Choose a digit in $$$k$$$ that is greater than $$$1$$$. If $$$k$$$ is divisible by that digit, divide $$$k$$$ by that digit. Repeat this process on the resulting number until either $$$1$$$ is reached or there are no more legal operations. Call $$$k$$$ valid if there exists a way to reduce it to $$$1$$$ via this operation.

Compute the number of $$$k$$$ in the range $$$1, \dots, N$$$ that are valid.

Input

The first line of input contains the given integer $$$N$$$ ($$$1 \le N \le 10^{18}$$$).

Output

Output a single line, with a single integer equivalent to the number of integers from $$$1$$$ to $$$N$$$ that have a way to reach $$$1$$$ using the operation.

Scoring

There are two subtasks for this problem.

  • ($$$25$$$ Points): $$$N \le 10^5$$$.
  • ($$$75$$$ Points): No additional constraints.
Examples
Input
9
Output
9
Input
13
Output
10
Note

In the first test case, all integers from $$$1$$$ to $$$9$$$ can be divided by themselves to reach $$$1$$$, so the answer is $$$9$$$.

In the second test case, all integers from $$$1$$$ to $$$9$$$ are valid, as mentioned in the first test case. $$$10$$$, $$$11$$$, and $$$13$$$ have no digits greater than $$$1$$$ that are divisors of themselves, and therefore cannot be reduced to $$$1$$$. However, $$$12$$$ can be divided by $$$2$$$ to get $$$6$$$, which can in turn be divided by $$$6$$$ to get $$$1$$$. Therefore, the numbers $$$1$$$ through $$$9$$$ and $$$12$$$ are valid, giving an answer of $$$10$$$.