#include <bits/stdc++.h>
using namespace std;
using INT = long long;
using pii = pair<int, int>;
int flag[10001000], ph[10001000], sum[10001000], p_cnt[10001000], tmp[10001000];
void pre() {
  for (int i = 2; i < 10001000; i++) {
    if (flag[i]) continue;
    for (int j = i; j < 10001000; j += i) {
      if (!flag[j]) flag[j] = i;
    }
  }
}
int b[10001000];
void update(int u) {
  for (; u < 10001000; u += u & -u) b[u]++;
}
int CALC(int u, int ans = 0) {
  for (; u; u -= u & -u) ans += b[u];
  return ans;
}
INT cnt[5];
int arr[10001000], nn;
void calc1() {
  for (int i = 2; i <= nn; i++) cnt[1] += (i - 1 - ph[i]);
  return;
}
void calc2(int n) {
  for (int i = 1; i <= nn; i++) {
    int x = arr[i];
    cnt[2] += ph[i];
    int q = n / flag[x];
    cnt[2] -= (CALC(10001000 - 1) - CALC(q));
    update(flag[x]);
  }
  return;
}
void solve(int n) {
  for (int i = 2; i <= n; i++) {
    tmp[i] = tmp[i - 1];
    if (flag[i] == i) tmp[i]++;
    if (flag[i] == i && 2 * i > n) continue;
    arr[++nn] = i;
  }
  if (nn <= 1) {
    puts("0");
    return;
  }
  INT tot = 1LL * nn * (nn - 1) / 2;
  for (int i = 1; i <= nn; i++) {
    sum[i] = sum[i - 1];
    int x = arr[i];
    if (flag[x] == x) sum[i]++;
    ph[i] = x;
    while (x > 1) {
      int p = flag[x];
      if (2 * p <= n) p_cnt[i]++;
      ph[i] /= p;
      ph[i] *= (p - 1);
      while (x % p == 0) x /= p;
    }
    ph[i]--;
    x = arr[i];
    if (x > n / 2) ph[i] -= (tmp[x] - tmp[n / 2]);
  }
  calc1();
  calc2(n);
  cnt[3] = tot - cnt[1] - cnt[2];
  INT ans = 0;
  for (int i = 1; i <= 3; i++) ans += i * cnt[i];
  cout << ans << endl;
  return;
}
int main() {
  pre();
  int n;
  cin >> n;
  solve(n);
  return 0;
}

### Prompt

Your task is to create a CPP solution to the following problem:

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;
using INT = long long;
using pii = pair<int, int>;
int flag[10001000], ph[10001000], sum[10001000], p_cnt[10001000], tmp[10001000];
void pre() {
  for (int i = 2; i < 10001000; i++) {
    if (flag[i]) continue;
    for (int j = i; j < 10001000; j += i) {
      if (!flag[j]) flag[j] = i;
    }
  }
}
int b[10001000];
void update(int u) {
  for (; u < 10001000; u += u & -u) b[u]++;
}
int CALC(int u, int ans = 0) {
  for (; u; u -= u & -u) ans += b[u];
  return ans;
}
INT cnt[5];
int arr[10001000], nn;
void calc1() {
  for (int i = 2; i <= nn; i++) cnt[1] += (i - 1 - ph[i]);
  return;
}
void calc2(int n) {
  for (int i = 1; i <= nn; i++) {
    int x = arr[i];
    cnt[2] += ph[i];
    int q = n / flag[x];
    cnt[2] -= (CALC(10001000 - 1) - CALC(q));
    update(flag[x]);
  }
  return;
}
void solve(int n) {
  for (int i = 2; i <= n; i++) {
    tmp[i] = tmp[i - 1];
    if (flag[i] == i) tmp[i]++;
    if (flag[i] == i && 2 * i > n) continue;
    arr[++nn] = i;
  }
  if (nn <= 1) {
    puts("0");
    return;
  }
  INT tot = 1LL * nn * (nn - 1) / 2;
  for (int i = 1; i <= nn; i++) {
    sum[i] = sum[i - 1];
    int x = arr[i];
    if (flag[x] == x) sum[i]++;
    ph[i] = x;
    while (x > 1) {
      int p = flag[x];
      if (2 * p <= n) p_cnt[i]++;
      ph[i] /= p;
      ph[i] *= (p - 1);
      while (x % p == 0) x /= p;
    }
    ph[i]--;
    x = arr[i];
    if (x > n / 2) ph[i] -= (tmp[x] - tmp[n / 2]);
  }
  calc1();
  calc2(n);
  cnt[3] = tot - cnt[1] - cnt[2];
  INT ans = 0;
  for (int i = 1; i <= 3; i++) ans += i * cnt[i];
  cout << ans << endl;
  return;
}
int main() {
  pre();
  int n;
  cin >> n;
  solve(n);
  return 0;
}

```