#include <bits/stdc++.h>
const int N = 1e7 + 5;
int P[N >> 3], phi[N], mu[N], mn[N], cnt[N];
void Init(const int n) {
  phi[1] = mu[1] = 1;
  for (int i = 2, cnt = 0; i <= n; ++i) {
    if (!mn[i]) P[++cnt] = mn[i] = i, phi[i] = i - 1, mu[i] = -1;
    for (int j = 1, v; j <= cnt && (v = i * P[j]) <= n; ++j) {
      mn[v] = P[j];
      if (i % P[j])
        phi[v] = phi[i] * (P[j] - 1), mu[v] = -mu[i];
      else {
        phi[v] = phi[i] * P[j], mu[v] = 0;
        break;
      }
    }
  }
}
int main() {
  int n;
  scanf("%d", &n);
  Init(n);
  long long ans = 0, t2 = 0, t3 = 0, tot = 0;
  for (int i = 2, half = n >> 1; i <= n; ++i)
    if (mn[i] != i || i <= half) ++tot, t2 += i - 1 - phi[i], ++cnt[mn[i]];
  tot = tot * (tot - 1) >> 1;
  for (int i = 2; i <= n; ++i) cnt[i] += cnt[i - 1];
  for (int i = 2, half = n >> 1; i <= n; ++i)
    if (mn[i] != i || i <= half) t3 += cnt[n / mn[i]];
  for (int d = 2, m = sqrt(n); d <= n; ++d) {
    long long tmp = 1ll * (n / d) * (n / d);
    if (d > m && mn[d] == d) --tmp;
    t3 += mu[d] * tmp;
  }
  t3 >>= 1, ans += t2 + (t3 << 1) + (tot - t2 - t3) * 3;
  printf("%I64d\n", ans);
  return 0;
}

### Prompt

Your challenge is to write 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>
const int N = 1e7 + 5;
int P[N >> 3], phi[N], mu[N], mn[N], cnt[N];
void Init(const int n) {
  phi[1] = mu[1] = 1;
  for (int i = 2, cnt = 0; i <= n; ++i) {
    if (!mn[i]) P[++cnt] = mn[i] = i, phi[i] = i - 1, mu[i] = -1;
    for (int j = 1, v; j <= cnt && (v = i * P[j]) <= n; ++j) {
      mn[v] = P[j];
      if (i % P[j])
        phi[v] = phi[i] * (P[j] - 1), mu[v] = -mu[i];
      else {
        phi[v] = phi[i] * P[j], mu[v] = 0;
        break;
      }
    }
  }
}
int main() {
  int n;
  scanf("%d", &n);
  Init(n);
  long long ans = 0, t2 = 0, t3 = 0, tot = 0;
  for (int i = 2, half = n >> 1; i <= n; ++i)
    if (mn[i] != i || i <= half) ++tot, t2 += i - 1 - phi[i], ++cnt[mn[i]];
  tot = tot * (tot - 1) >> 1;
  for (int i = 2; i <= n; ++i) cnt[i] += cnt[i - 1];
  for (int i = 2, half = n >> 1; i <= n; ++i)
    if (mn[i] != i || i <= half) t3 += cnt[n / mn[i]];
  for (int d = 2, m = sqrt(n); d <= n; ++d) {
    long long tmp = 1ll * (n / d) * (n / d);
    if (d > m && mn[d] == d) --tmp;
    t3 += mu[d] * tmp;
  }
  t3 >>= 1, ans += t2 + (t3 << 1) + (tot - t2 - t3) * 3;
  printf("%I64d\n", ans);
  return 0;
}

```