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>
using namespace std;
int IN() {
  int c, f, x;
  while (!isdigit(c = getchar()) && c != '-')
    ;
  c == '-' ? (f = 1, x = 0) : (f = 0, x = c - '0');
  while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + c - '0';
  return !f ? x : -x;
}
const int top = 10000000;
const int N = top + 19;
int vis[N], pri[N], mu[N], minp[N], sum[N], num[N];
int n;
long long ans, tmp;
void Init(int top) {
  mu[1] = 1;
  for (int i = 2; i < top + 1; i++) {
    if (!vis[i]) {
      pri[++*pri] = i;
      minp[i] = i;
      mu[i] = -1;
    }
    for (int j = 1; j <= *pri && pri[j] * i <= top; j++) {
      vis[pri[j] * i] = 1;
      minp[pri[j] * i] = pri[j];
      if (i % pri[j] == 0) {
        mu[pri[j] * i] = 0;
        break;
      } else {
        mu[pri[j] * i] = -mu[i];
      }
    }
  }
  for (int i = 2; i < top + 1; i++) sum[i] = sum[i - 1] + (!vis[i]);
}
int cal(int l, int r) {
  if (l > r) return 0;
  return sum[r] - sum[l - 1];
}
int main() {
  n = IN();
  Init(n);
  for (int i = 2; i < n + 1; i++)
    if (!vis[i]) {
      ans += 2ll * sum[n / i];
      if (2 * i <= n) ans += 3ll * cal(n / i + 1, n / 2);
    }
  for (int i = 1; i < n + 1; i++) {
    int alb;
    if (i == 1)
      alb = n - 1 - *pri;
    else if (vis[i])
      alb = n / i;
    else
      alb = n / i - 1;
    tmp += 1ll * mu[i] * alb * alb;
  }
  ans += 2 * tmp;
  ans += 1ll * (n - 1 - *pri) * (n - 1 - *pri) - tmp;
  for (int i = 2; i < n + 1; i++)
    if (!vis[i]) ans += 2 * (n / i - 1);
  for (int i = 2; i < n + 1; i++)
    if (vis[i]) num[minp[i]]++;
  for (int i = 2; i < n + 1; i++)
    if (num[i]) {
      ans += 4ll * num[i] * cal(1, n / i);
      if (2 * i <= n) ans += 6ll * num[i] * cal(n / i + 1, n / 2);
    }
  for (int i = 2; i < n + 1; i++)
    if (!vis[i]) {
      for (int j = i + i; j <= n; j += i) {
        if (1ll * i * minp[j] <= n)
          ans -= 4;
        else if (2ll * max(i, minp[j]) <= n)
          ans -= 6;
      }
    }
  for (int i = 2; i < n + 1; i++)
    if (!vis[i]) {
      if (1ll * i * i <= n)
        ans -= 2;
      else if (2ll * i <= n)
        ans -= 3;
    } else
      ans--;
  ans /= 2;
  cout << ans << endl;
}