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.

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

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

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