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.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
const int N = 10000010;
int min[N], cnt[N], phi[N], mu[N];
long long ans[N];
std::vector<int> prime;
int main() {
  int n;
  scanf("%d", &n);
  phi[1] = 1;
  for (int i = 2; i <= n; ++i) {
    if (!min[i]) {
      min[i] = i;
      phi[i] = i - 1;
      prime.push_back(i);
      mu[i] = -1;
    }
    for (int j = 0, k, sz = (int)prime.size(); j < sz && i * prime[j] <= n;
         ++j) {
      min[k = i * prime[j]] = prime[j];
      if (i % prime[j] == 0) {
        phi[k] = phi[i] * prime[j];
        mu[k] = 0;
        break;
      }
      phi[k] = phi[i] * (prime[j] - 1);
      mu[k] = -mu[i];
    }
    ++cnt[min[i]];
  }
  long long cnt0 = 1;
  for (auto u : prime) {
    cnt0 += u << 1 > n;
  }
  cnt0 = cnt0 * (n - cnt0) + cnt0 * (cnt0 - 1) / 2;
  long long cnt1 = 1ll * n * (n - 1) >> 1;
  for (int i = 2; i <= n; ++i) {
    cnt1 -= phi[i];
  }
  long long cnt2 = 0;
  for (int i = 0, sz = prime.size(); i < sz; ++i) {
    for (int j = 0; j < sz; ++j) {
      if (prime[i] * prime[j] > n) break;
      if (prime[i] == prime[j]) continue;
      cnt2 += 1ll * cnt[prime[i]] * cnt[prime[j]];
    }
  }
  for (auto u : prime) {
    cnt2 += 1ll * cnt[u] * cnt[u];
  }
  for (int i = 2; i <= n; ++i) {
    ans[i] = 1ll * (n / i) * (n / i);
    if (1ll * min[i] * min[i] > n) {
      for (int j = i << 1; j <= n; j += i) {
        if (1ll * min[j] * min[i] > n) {
          ans[i] -= 2;
        }
      }
    }
  }
  for (int i = 2; i <= n; ++i) {
    for (int j = i << 1; j <= n; j += i) {
      ans[i] += ans[j] * mu[j / i];
    }
    cnt2 -= ans[i];
  }
  cnt2 >>= 1;
  long long cnt3 = 1ll * n * (n - 1) / 2 - cnt0 - cnt1 - cnt2;
  return printf("%I64d\n", cnt1 + 2 * cnt2 + 3 * cnt3), 0;
}