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;
const int MOD = 1000000007;
const int UNDEF = -1;
const long long INF = 1e18;
template <typename T>
inline bool chkmax(T &aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T &aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
int rint();
char rch();
long long rlong();
const int MAXN = 1e7 + 1;
const int MAXP = MAXN;
int mu[MAXP], ptbl[MAXP];
vector<int> primes;
void sieve(int maxp) {
  maxp++;
  mu[1] = ptbl[1] = 1;
  for (int i = 2; i < maxp; i++) {
    if (!ptbl[i]) {
      ptbl[i] = i;
      primes.push_back(i);
      mu[i] = -1;
    }
    for (auto p : primes) {
      int x = i * p;
      if (x >= maxp) break;
      if (!ptbl[x]) ptbl[x] = p;
      mu[x] = -mu[i];
      if (i % p == 0) {
        mu[x] = 0;
        break;
      }
    }
  }
}
const int MAXFAC = 24;
pair<int, int> factorize_dest[MAXFAC];
int factorize_tmp[MAXFAC];
int factorize(int x) {
  int tsz = 0;
  while (x > 1) {
    int p = ptbl[x];
    x /= p;
    factorize_tmp[tsz++] = p;
  }
  sort(factorize_tmp, factorize_tmp + tsz);
  int didx = 0;
  for (int tidx = 0; tidx < tsz; tidx++) {
    int p = factorize_tmp[tidx];
    if (tidx == 0 || p != factorize_tmp[tidx - 1]) {
      factorize_dest[didx++] = make_pair(p, 1);
    } else
      factorize_dest[didx - 1].second++;
  }
  return didx;
}
const int MAXDIV = 4096;
int divisors_dest[MAXDIV];
int getdivisors(int x) {
  int numprimes = factorize(x);
  int sz = 1;
  divisors_dest[0] = 1;
  for (int pi = 0; pi < numprimes; pi++) {
    int p = factorize_dest[pi].first;
    int elim = factorize_dest[pi].second;
    int pp = 1;
    int prevsz = sz;
    for (int e = 1; e <= elim; e++) {
      pp *= p;
      for (int i = 0; i < prevsz; i++) {
        divisors_dest[sz++] = divisors_dest[i] * pp;
      }
    }
  }
  return sz;
}
int quon[MAXN];
int n, sqrtn;
int vp[MAXN];
int spcnt[MAXN];
int main() {
  scanf("%d", &n);
  sieve(n);
  int special1 = 3 * n - 2;
  sqrtn = round(sqrt(n));
  if ((sqrtn * sqrtn) > n) sqrtn--;
  quon[1] = n;
  long long final1 = 0;
  for (int d = 2; d <= n; d++) {
    int mud = mu[d];
    if (mud == 0) continue;
    int nd = n / d;
    quon[d] = nd;
    long long contrib = nd * (long long)(mud * nd);
    final1 -= contrib;
  }
  final1 -= (n - 1);
  long long final2 = 0;
  for (int d = 2; d <= n; d++) {
    int mud = mu[d];
    if (mud == 0) continue;
    int vpsz = 0;
    for (int x = max(2, d); x <= n; x += d) {
      vp[vpsz++] = ptbl[x];
    }
    sort(vp, vp + vpsz);
    int r = vpsz - 1;
    long long collect = 0;
    for (int l = 0; l < vpsz; l++) {
      int p = vp[l];
      int pn = quon[p];
      while (r >= 0 && vp[r] > pn) r--;
      collect += (r + 1);
    }
    final2 += collect * mu[d];
  }
  for (int x = 2; x <= n; x++) spcnt[ptbl[x]]++;
  for (int x = 2; x <= n; x++) spcnt[x] += spcnt[x - 1];
  for (int p = 2; p <= n; p++) {
    final2 += (spcnt[p] - spcnt[p - 1]) * (long long)spcnt[quon[p]];
  }
  long long final0 = 0;
  for (int a = 2; a <= n; a++) {
    int spa = ptbl[a];
    int lower;
    if (spa <= (n >> 1)) {
      lower = (n >> 1);
    } else {
      lower = quon[spa];
    }
    int imin = 0, imax = primes.size();
    while (imin < imax) {
      int imid = (imin + imax) >> 1;
      if (primes[imid] <= lower)
        imin = imid + 1;
      else
        imax = imid;
    }
    int ans = spcnt[n] - (imin > 0 ? spcnt[primes[imin - 1]] : 0);
    if (ptbl[a] == a && a > lower) {
      ans -= (spcnt[a] - spcnt[a - 1]);
    }
    final0 += ans;
  }
  long long final3 = n * (long long)n - final0 - final1 - final2 - special1;
  long long final = (final1 + 2 * final2 + 3 * final3) >> 1;
  printf("%lld\n", final);
}