CF870F.Paths

You are given a positive integer n. Let's build a graph on vertices 1, 2, ..., n in such a way that there is an edge between vertices u and v if and only if . Let d(u, v) be the shortest distance between u and v, or 0 if there is no path between them. Compute the sum of values d(u, v) over all 1 ≤ u < v ≤ n.

The gcd (greatest common divisor) of two positive integers is the maximum positive integer that divides both of the integers.

给定一个正整数 $n$。我们构造一个以顶点 $1, 2, \dots, n$ 为节点的图，其中顶点 $u$ 与 $v$ 之间存在一条边当且仅当 。令 $d(u, v)$ 表示 $u$ 与 $v$ 之间的最短距离；若 $u$ 与 $v$ 之间不存在路径，则 $d(u, v) = 0$。请计算所有满足 $1 \le u < v \le n$ 的 $d(u, v)$ 之和。

两个正整数的 gcd（最大公约数）是指能同时整除这两个正整数的最大正整数。

Single integer n (1 ≤ n ≤ 107).

单个整数 $n$（$1 \leq n \leq 10^7$）。

Print the sum of d(u, v) over all 1 ≤ u < v ≤ n.

输出所有满足 $1 \leq u < v \leq n$ 的 $d(u, v)$ 的总和。

All shortest paths in the first example:

• 
• 
• 
• 
• 
• 

There are no paths between other pairs of vertices.

The total distance is 2 + 1 + 1 + 2 + 1 + 1 = 8.

第一个示例中所有最短路径：

• 
• 
• 
• 
• 
• 

其余顶点对之间不存在路径。

总距离为 $2 + 1 + 1 + 2 + 1 + 1 = 8$。