Background

Will you think of tomorrow,

the problems you did not finish debugging yesterday?

Will you still remember tomorrow,

the brute force that failed in the contest?

OEIS Link

Problem 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