34490번 - Number Reduction 서브태스크다국어

문제

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.

입력

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

출력

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.

제한

서브태스크

노트

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