A11185 | 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.

Single integer $n$ ( $1<=n<=10^{7}$ ).

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