No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Paths

time limit per test

4 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou 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.

Input

Single integer *n* (1 ≤ *n* ≤ 10^{7}).

Output

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

Examples

Input

6

Output

8

Input

10

Output

44

Note

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.

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/17/2022 06:47:41 (k1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|