Coprime Graph

Time limit1sMemory limit512 MB

Summary

Count pairs (a, b) with 1 <= a < b <= N whose greatest common divisor is 1.

Level: Medium4 of 10
Topics: Math, Number theory, Combinatorics, Prefix sum
Solved: No attempts yet

Problem

Wooshik draws a graph whenever he is bored. He draws a new graph every month, and this month he is drawing a coprime graph.

The coprime graph has $N$ vertices numbered $1$ through $N$ . Two distinct vertices are directly connected by an edge only when their numbers are coprime.

Wooshik is curious how many edges he has to draw. Given the number of vertices $N$ , find the number of edges he must draw.

Input

The first line gives the number of vertices $N$ of the graph.

Output

Print the number of edges Wooshik has to draw.

Constraints

$1 \leq N \leq 50\,000$

Examples1

Example 1
Input
```
10
```
Expected output
```
31
```