Description

Back in elementary school, Little Z had already started learning OI.

Once in a math class, the teacher asked this question: Find the number of ordered integer pairs $(x, y)$ such that $1 \le x, y \le 5$ and $\frac{x}{y}$ can be written as a terminating decimal.

Of course, Little Z quickly worked it out.

But since he had learned OI, he generalized it:

Given a positive integer $n$, find the number of ordered integer pairs $(x, y)$ such that $1 \le x, y \le n$ and $\frac{x}{y}$ can be written as a terminating decimal.

At that time, he was still a newbie (cai ji, “菜鸡”) and only knew the $O(n^2)$ brute force.

A few years later, he happened to see this problem again. Now he knows a better method, so he turned it into a problem for you to solve.

Input Format

One line containing a positive integer $n$.

Output Format

One line containing an integer, the answer.

3

7

5

21

Hint

Explanation for Sample 1

$\frac{1}{1}$, $\frac{1}{2}$, $\frac{2}{1}$, $\frac{2}{2}$, $\frac{3}{1}$, $\frac{3}{2}$, $\frac{3}{3}$ can all be written as terminating decimals.

Constraints

• Subtask 1 (40 points), $1 \le n \le 10^3$.
• Subtask 2 (40 points), $1 \le n \le 10^7$.
• Subtask 3 (20 points), $1 \le n \le 10^{12}$.

Translated by ChatGPT 5