题目描述

在算法竞赛的数论知识中，我们接触过埃拉托斯特尼筛法、线性筛法、莫比乌斯反演、杜教筛、Powerful Number 筛、Min_25 筛、洲阁筛等算法来帮助我们优化一些求和/连乘的复杂度，那么现在问题来了，今天这道题将会使用到上述的哪个算法呢？

现在给定正整数 $n$，需要你求

$$\sum\limits_{i=1}^n\sum\limits_{j=1}^n\lfloor \dfrac{n}{\max(i,j)}\rfloor [i \perp j] $$

其中 $[i \perp j]$ 表示 $i,j$ 是否互素，即当 $\gcd(i,j)=1$ 时，$[i \perp j]$ 的值为 $1$，其余情况其值为 $0$。

输入格式

输入一行一个正整数 $n$ ($1\le n \le 10^9$)。

输出格式

输出一行一个整数，表示这个和式的结果。

2

4