#include <bits/stdc++.h>
using namespace std;
template <typename T>
void get_int(T &x) {
  char t = getchar();
  bool neg = false;
  x = 0;
  for (; (t > '9' || t < '0') && t != '-'; t = getchar())
    ;
  if (t == '-') neg = true, t = getchar();
  for (; t <= '9' && t >= '0'; t = getchar()) x = x * 10 + t - '0';
  if (neg) x = -x;
}
template <typename T>
void print_int(T x) {
  if (x < 0) putchar('-'), x = -x;
  short a[20] = {}, sz = 0;
  while (x > 0) a[sz++] = x % 10, x /= 10;
  if (sz == 0) putchar('0');
  for (int i = sz - 1; i >= 0; i--) putchar('0' + a[i]);
}
const int inf = 0x3f3f3f3f;
const long long Linf = 1ll << 61;
const double pi = acos(-1.0);
const int maxn = 10000111;
bool pr[maxn];
int n, mnv[maxn], miu[maxn], prm[1000111], tot, cnt[maxn];
int main() {
  get_int(n);
  for (int i = 1; i <= n; i++) {
    miu[i] = 1;
    pr[i] = (i > 1);
  }
  for (int i = 2; i <= n; i++) {
    if (pr[i]) {
      prm[++tot] = mnv[i] = i;
      miu[i] = -1;
      for (int j = i + i; j <= n; j += i) {
        pr[j] = 0;
        if (mnv[j] == 0) mnv[j] = i;
        if (j / i % i == 0)
          miu[j] = 0;
        else
          miu[j] *= -1;
      }
    }
  }
  long long ans1 = 0, ans2 = 0, ans3 = 0;
  for (int i = 1; i <= n; i++) {
    cnt[mnv[i]]++;
    ans1 += 1ll * miu[i] * (n / i) * (n / i);
  }
  ans1 = (1ll * n * n - ans1) - (n - 1) >> 1;
  int cur = tot, tot2 = 0;
  for (int i = 1; prm[i] * prm[i] <= n; i++) {
    while (cur >= 1 && 1ll * prm[i] * prm[cur] > n) {
      tot2 += cnt[prm[cur]];
      cur--;
    }
    ans2 += 1ll * cnt[prm[i]] * tot2;
  }
  tot2 = 0;
  for (int i = tot; i >= 1 && 1ll * prm[i] * prm[i] > n; i--) {
    ans2 += 1ll * tot2 * cnt[prm[i]];
    tot2 += cnt[prm[i]];
  }
  cur = tot;
  tot2 = 0;
  while (cur >= 1 && 2 * prm[cur] > n) cur--;
  for (int i = 1; prm[i] * prm[i] <= n; i++) {
    while (cur >= 1 && 1ll * prm[i] * prm[cur] > n) {
      tot2 += cnt[prm[cur]];
      cur--;
    }
    ans3 += 1ll * cnt[prm[i]] * tot2;
  }
  cur = tot;
  tot2 = 0;
  while (cur >= 1 && 2 * prm[cur] > n) cur--;
  for (int i = cur; i >= 1 && 1ll * prm[i] * prm[i] > n; i--) {
    ans3 += 1ll * tot2 * cnt[prm[i]];
    tot2 += cnt[prm[i]];
  }
  ans2 -= ans3;
  print_int(1ll * (n - 1) * (n - 2) - ans1 - ans2 * 2 + ans3), puts("");
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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;
template <typename T>
void get_int(T &x) {
  char t = getchar();
  bool neg = false;
  x = 0;
  for (; (t > '9' || t < '0') && t != '-'; t = getchar())
    ;
  if (t == '-') neg = true, t = getchar();
  for (; t <= '9' && t >= '0'; t = getchar()) x = x * 10 + t - '0';
  if (neg) x = -x;
}
template <typename T>
void print_int(T x) {
  if (x < 0) putchar('-'), x = -x;
  short a[20] = {}, sz = 0;
  while (x > 0) a[sz++] = x % 10, x /= 10;
  if (sz == 0) putchar('0');
  for (int i = sz - 1; i >= 0; i--) putchar('0' + a[i]);
}
const int inf = 0x3f3f3f3f;
const long long Linf = 1ll << 61;
const double pi = acos(-1.0);
const int maxn = 10000111;
bool pr[maxn];
int n, mnv[maxn], miu[maxn], prm[1000111], tot, cnt[maxn];
int main() {
  get_int(n);
  for (int i = 1; i <= n; i++) {
    miu[i] = 1;
    pr[i] = (i > 1);
  }
  for (int i = 2; i <= n; i++) {
    if (pr[i]) {
      prm[++tot] = mnv[i] = i;
      miu[i] = -1;
      for (int j = i + i; j <= n; j += i) {
        pr[j] = 0;
        if (mnv[j] == 0) mnv[j] = i;
        if (j / i % i == 0)
          miu[j] = 0;
        else
          miu[j] *= -1;
      }
    }
  }
  long long ans1 = 0, ans2 = 0, ans3 = 0;
  for (int i = 1; i <= n; i++) {
    cnt[mnv[i]]++;
    ans1 += 1ll * miu[i] * (n / i) * (n / i);
  }
  ans1 = (1ll * n * n - ans1) - (n - 1) >> 1;
  int cur = tot, tot2 = 0;
  for (int i = 1; prm[i] * prm[i] <= n; i++) {
    while (cur >= 1 && 1ll * prm[i] * prm[cur] > n) {
      tot2 += cnt[prm[cur]];
      cur--;
    }
    ans2 += 1ll * cnt[prm[i]] * tot2;
  }
  tot2 = 0;
  for (int i = tot; i >= 1 && 1ll * prm[i] * prm[i] > n; i--) {
    ans2 += 1ll * tot2 * cnt[prm[i]];
    tot2 += cnt[prm[i]];
  }
  cur = tot;
  tot2 = 0;
  while (cur >= 1 && 2 * prm[cur] > n) cur--;
  for (int i = 1; prm[i] * prm[i] <= n; i++) {
    while (cur >= 1 && 1ll * prm[i] * prm[cur] > n) {
      tot2 += cnt[prm[cur]];
      cur--;
    }
    ans3 += 1ll * cnt[prm[i]] * tot2;
  }
  cur = tot;
  tot2 = 0;
  while (cur >= 1 && 2 * prm[cur] > n) cur--;
  for (int i = cur; i >= 1 && 1ll * prm[i] * prm[i] > n; i--) {
    ans3 += 1ll * tot2 * cnt[prm[i]];
    tot2 += cnt[prm[i]];
  }
  ans2 -= ans3;
  print_int(1ll * (n - 1) * (n - 2) - ans1 - ans2 * 2 + ans3), puts("");
  return 0;
}

```