回首过去

>明天你是否会想起 > >昨天未调完的题 > >明天你是否还惦记 > >考场写挂的暴力 [OEIS 入口](http://oeis.org/)

在小学时，小 Z 就已经开始学 OI 了。 有一次，在数学课上，老师问了这样一个问题： 求出有序整数对 $(x,y)$ 的个数，满足 $1\le x,y\le 5$ 且 $\frac{x}{y}$ 可以表示为十进制有限小数。 当然，小 Z 很快就算了出来。 但因为他是学了 OI 的，所以他就推广了一下： **给定正整数 $n$，求出有序整数对 $(x,y)$ 的个数，满足 $1\le x,y\le n$ 且 $\frac{x}{y}$ 可以表示为十进制有限小数。** 当时，他还是一个菜鸡，只会 $O(n^2)$ 的暴力。 过了几年，他偶然又翻到了这道题。现在他会了一种更好的方法，于是就把这题出了出来，给你来做做。

一行一个正整数 $n$。

一行一个整数表示答案。

3

7

5

21

**样例 1 解释** $\frac{1}{1}$，$\frac{1}{2}$，$\frac{2}{1}$，$\frac{2}{2}$，$\frac{3}{1}$，$\frac{3}{2}$，$\frac{3}{3}$ 都可以表示为十进制有限小数。 **数据规模与约定** * Subtask 1（40 分），$1 \le n \le 10^3$； * Subtask 2（40 分），$1 \le n \le 10^7$； * Subtask 3（20 分），$1 \le n \le 10^{12}$。