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;
void Freopen() {
  freopen(
      "title"
      ".in",
      "r", stdin);
  freopen(
      "title"
      ".out",
      "w", stdout);
}
int read() {
  int g = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || '9' < ch) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while ('0' <= ch && ch <= '9') {
    g = g * 10 + ch - '0';
    ch = getchar();
  }
  return g * f;
}
const int N = 1e7 + 5;
bool vis[N];
int p[N / 10], mn[N], smu[N], st[N], sst[N], mu[N];
int n;
long long ans1, ans2, ans3;
void init() {
  smu[1] = 1;
  for (int i = (2); i <= (n); i++) {
    if (!vis[i]) p[++p[0]] = i, mu[i] = -1, mn[i] = i, st[i]++;
    for (int j = 1; j <= p[0] && i * p[j] <= n; j++) {
      mn[i * p[j]] = p[j], st[p[j]]++;
      vis[i * p[j]] = 1;
      if (!(i % p[j])) break;
      mu[i * p[j]] = -mu[i];
    }
    smu[i] = smu[i - 1] + mu[i];
  }
  for (int i = (1); i <= (n); i++) sst[i] = sst[i - 1] + st[i];
}
long long calc(int x) { return 1ll * x * x; }
signed main() {
  n = read();
  init();
  long long re1 = 0;
  for (int l = 1, r; l <= n; l = r + 1) {
    r = n / (n / l);
    re1 += 1ll * (smu[r] - smu[l - 1]) * calc(n / l);
  }
  ans1 = (1ll * n * n - (n - 1) - re1) / 2;
  long long re2 = 0;
  for (int i = (1); i <= (n / 2); i++)
    re2 += 1ll * st[i] * sst[min(n / i, n / 2)];
  for (int i = 1; i * i <= n; i++) re2 -= st[i];
  re2 /= 2;
  re2 -= ans1;
  ans2 = re2;
  long long re3 = 1ll * sst[n / 2] * sst[n / 2];
  for (int i = (1); i <= (n / 2); i++) re3 -= st[i];
  re3 /= 2;
  re3 -= ans2 + ans1;
  ans3 = re3;
  cout << ans1 + 2 * ans2 + 3 * ans3;
  return signed();
}