P6583 Looking Back

> 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](http://oeis.org/)

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.

One line containing a positive integer $n$.

One line containing an integer, the answer.

**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