题目描述

给定正整数 $n$，计算下式的结果：

$$\sum_{i=1}^{n}\sum_{j=1}^{n}\lfloor\frac{n}{\max(i, j)}\rfloor[i \perp j]$$

其中 $\lfloor x \rfloor$ 表示对 $x$ 下取整；$[i \perp j]$ 表示 $i$ 与 $j$ 是否互素，即当 $\gcd(i, j) = 1$ 时，$[i \perp j]$ 的值为 $1$，否则为 $0$。

输入格式

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

输出格式

输出一个正整数，表示上式的值。

样例

2

4

数据范围

有 $25$ 个测试点。

对于前 $10$ 个测试点，$1\le n \le 5\times10^3$。

对于后 $15$ 个测试点，$1\le n \le 10^9$。