#include <bits/stdc++.h>
using namespace std;
const int maxn = 1E7 + 77;
int minDis[maxn], cPrimes = 0, u[maxn], cnt[maxn];
long long primes[maxn], sum[maxn];
void init(int n) {
  minDis[1] = u[1] = 1;
  for (int i = 2; i <= n; ++i) {
    if (minDis[i]) {
      int t = i / minDis[i];
      if (minDis[i] == minDis[t])
        u[i] = 0;
      else
        u[i] = -u[t];
    } else {
      minDis[i] = i;
      primes[cPrimes++] = i;
      u[i] = -1;
    }
    ++cnt[minDis[i]];
    for (int j = 0; j < cPrimes; ++j) {
      if (1ll * i * primes[j] > n) break;
      minDis[i * primes[j]] = primes[j];
      if (!(i % primes[j])) break;
    }
  }
  for (int i = 1; i <= n; ++i) {
    sum[i] = sum[i - 1] + cnt[i];
  }
}
long long N, C[4];
int main() {
  cin >> N;
  init(N);
  C[0] = 1;
  for (int i = 0; i < cPrimes; ++i)
    if (primes[i] <= N && (primes[i] << 1) > N) ++C[0];
  C[0] = N * N - (N - C[0]) * (N - C[0]) + N - C[0];
  for (int i = 1; i <= N; ++i)
    if (u[i]) C[1] += (N / i) * (N / i) * u[i];
  C[1] = N * N - C[1];
  C[1] -= N - 1;
  int p = cPrimes;
  for (int i = 0; i < cPrimes; ++i) {
    while (p && primes[p - 1] > N || primes[p - 1] * primes[i] > N) --p;
    C[2] += cnt[primes[i]] * sum[primes[p - 1]];
  }
  for (int i = 0; i < cPrimes; ++i)
    if ((primes[i] * primes[i]) <= N) {
      C[2] -= cnt[primes[i]];
    }
  C[2] -= C[1];
  C[3] = N * N;
  for (int i = 0; i < 3; ++i) C[3] -= C[i];
  long long ans = 0;
  for (int i = 0; i < 4; ++i) {
    ans += C[i] * i;
  }
  cout << (ans >> 1) << endl;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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 <image>. 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 ≤ 107).

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: 

  * <image>
  * <image>
  * <image>
  * <image>
  * <image>
  * <image>



There are no paths between other pairs of vertices.

The total distance is 2 + 1 + 1 + 2 + 1 + 1 = 8.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1E7 + 77;
int minDis[maxn], cPrimes = 0, u[maxn], cnt[maxn];
long long primes[maxn], sum[maxn];
void init(int n) {
  minDis[1] = u[1] = 1;
  for (int i = 2; i <= n; ++i) {
    if (minDis[i]) {
      int t = i / minDis[i];
      if (minDis[i] == minDis[t])
        u[i] = 0;
      else
        u[i] = -u[t];
    } else {
      minDis[i] = i;
      primes[cPrimes++] = i;
      u[i] = -1;
    }
    ++cnt[minDis[i]];
    for (int j = 0; j < cPrimes; ++j) {
      if (1ll * i * primes[j] > n) break;
      minDis[i * primes[j]] = primes[j];
      if (!(i % primes[j])) break;
    }
  }
  for (int i = 1; i <= n; ++i) {
    sum[i] = sum[i - 1] + cnt[i];
  }
}
long long N, C[4];
int main() {
  cin >> N;
  init(N);
  C[0] = 1;
  for (int i = 0; i < cPrimes; ++i)
    if (primes[i] <= N && (primes[i] << 1) > N) ++C[0];
  C[0] = N * N - (N - C[0]) * (N - C[0]) + N - C[0];
  for (int i = 1; i <= N; ++i)
    if (u[i]) C[1] += (N / i) * (N / i) * u[i];
  C[1] = N * N - C[1];
  C[1] -= N - 1;
  int p = cPrimes;
  for (int i = 0; i < cPrimes; ++i) {
    while (p && primes[p - 1] > N || primes[p - 1] * primes[i] > N) --p;
    C[2] += cnt[primes[i]] * sum[primes[p - 1]];
  }
  for (int i = 0; i < cPrimes; ++i)
    if ((primes[i] * primes[i]) <= N) {
      C[2] -= cnt[primes[i]];
    }
  C[2] -= C[1];
  C[3] = N * N;
  for (int i = 0; i < 3; ++i) C[3] -= C[i];
  long long ans = 0;
  for (int i = 0; i < 4; ++i) {
    ans += C[i] * i;
  }
  cout << (ans >> 1) << endl;
}

```