#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e7 + 8;
int pr[maxn];
bool sv[maxn];
int phi[maxn];
int bit[maxn];
void upd(int x) {
  while (x < maxn) {
    bit[x]++;
    x += x & (-x);
  }
}
int qry(int x) {
  int ans = 0;
  while (x > 0) {
    ans += bit[x];
    x -= x & (-x);
  }
  return ans;
}
int main() {
  int n;
  scanf("%d", &n);
  fill(pr, pr + maxn, 1);
  fill(sv, sv + maxn, true);
  fill(phi, phi + maxn, 1);
  long long badp = 0;
  for (int p = 2; p <= n; p++) {
    if (!sv[p]) continue;
    pr[p] = p;
    phi[p] = p - 1;
    for (int z = p + p; z <= n; z += p) {
      int ex = 1;
      int u = z;
      while (u % p == 0) {
        ex *= p;
        u /= p;
      }
      phi[z] = phi[z] * (ex / p) * (p - 1);
      if (pr[z] == 1) pr[z] = p;
      sv[z] = false;
    }
    if (p > n / 2) badp++;
  }
  long long tot = (long long)n * (n - 1) / 2;
  long long zero =
      ((long long)n - 1 - badp) * badp + badp * (badp - 1) / 2 + n - 1;
  long long one = 0, two = 0;
  for (int z = 2; z <= n; z++) {
    one += z - 1 - phi[z];
  }
  for (int z = 2; z <= n; z++) {
    long long q = qry(n / pr[z]);
    two += q - (z - 1 - phi[z]);
    upd(pr[z]);
  }
  long long three = tot - zero - one - two;
  printf("%lld", one + two * 2 + three * 3);
  printf("\n");
}

### 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 + 8;
int pr[maxn];
bool sv[maxn];
int phi[maxn];
int bit[maxn];
void upd(int x) {
  while (x < maxn) {
    bit[x]++;
    x += x & (-x);
  }
}
int qry(int x) {
  int ans = 0;
  while (x > 0) {
    ans += bit[x];
    x -= x & (-x);
  }
  return ans;
}
int main() {
  int n;
  scanf("%d", &n);
  fill(pr, pr + maxn, 1);
  fill(sv, sv + maxn, true);
  fill(phi, phi + maxn, 1);
  long long badp = 0;
  for (int p = 2; p <= n; p++) {
    if (!sv[p]) continue;
    pr[p] = p;
    phi[p] = p - 1;
    for (int z = p + p; z <= n; z += p) {
      int ex = 1;
      int u = z;
      while (u % p == 0) {
        ex *= p;
        u /= p;
      }
      phi[z] = phi[z] * (ex / p) * (p - 1);
      if (pr[z] == 1) pr[z] = p;
      sv[z] = false;
    }
    if (p > n / 2) badp++;
  }
  long long tot = (long long)n * (n - 1) / 2;
  long long zero =
      ((long long)n - 1 - badp) * badp + badp * (badp - 1) / 2 + n - 1;
  long long one = 0, two = 0;
  for (int z = 2; z <= n; z++) {
    one += z - 1 - phi[z];
  }
  for (int z = 2; z <= n; z++) {
    long long q = qry(n / pr[z]);
    two += q - (z - 1 - phi[z]);
    upd(pr[z]);
  }
  long long three = tot - zero - one - two;
  printf("%lld", one + two * 2 + three * 3);
  printf("\n");
}

```