Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

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-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/10/2018 21:55:44 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|