题目背景

明天你是否会想起

昨天未调完的题

明天你是否还惦记

考场写挂的暴力

OEIS 入口

题目描述

在小学时，小 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}$。