给定一个正整数 n。让我们在顶点 1, 2, ..., n 上构建一个图,使得顶点 u 和 v 之间存在边当且仅当 $${ \mathrm { g c d } } ( u, v ) \neq 1$$。令 d(u, v) 为 u 和 v 之间的最短距离,如果它们之间没有路径,则为 0。计算所有 1 ≤ u < v ≤ n 的值 d(u, v) 之和。
两个正整数的 gcd(最大公约数)是整除这两个整数的最大正整数。
输入
单个整数 n (1 ≤ n ≤ 107)。
输出
打印所有 1 ≤ u < v ≤ n 上 d(u, v) 的总和。
示例
输入 #1
6
输出 #1
8
输入 #2
10
输出 #2
44
注意
第一个示例中的所有最短路径:
- $$2 \右箭头 6 \右箭头 3$$
- $$2 \右箭头 4$$
- $$2 \右箭头 6$$
- $$3 \右箭头 6 \右箭头 4$$
- $$3 \右箭头 6$$
- $$\overrightarrow{4} \to \overrightarrow{6}$$
其他顶点对之间没有路径。
总距离为 2 + 1 + 1 + 2 + 1 + 1 = 8。