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>
template <class T>
class _Fenwick {
 private:
  std::vector<T> sum;
  int _size;

 public:
  _Fenwick() { _size = 0; }
  void reset(int n) {
    _size = n;
    sum.clear();
    sum.resize(n + 1);
  }
  void add(int x, T y) {
    while (x <= _size) {
      sum[x] += y;
      x += x & -x;
    }
  }
  T query(int x, T y) {
    T ans = y;
    while (x) {
      ans += sum[x];
      x -= x & -x;
    };
    return ans;
  }
  void build(T *a, int n) {
    reset(n);
    for (int i = 1; i <= n; ++i) add(i, a[i]);
  }
};
template <typename T>
void read(T &x);
template <typename T>
void read(T &x, T &y);
template <typename T>
void read(T &x, T &y, T &z);
template <typename T>
void write(T x);
template <typename T>
void writeC(T x);
template <typename T>
void writeN(T x);
template <typename T>
void _binary(T x, int len);
long long _qpow(long long a, long long b, long long M);
long long _inv(long long x, long long M);
int prime[10000005], mu[10000005], not_prime[10000005], n, vis[10000005], tl,
    d[10000005];
void sieve(int lim) {
  mu[1] = 1;
  for (int i = 2; i <= lim; ++i) {
    if (!not_prime[i]) {
      prime[++tl] = i;
      mu[i] = -1;
    }
    for (int j = 1; j <= tl && (long long)i * prime[j] <= lim; ++j) {
      not_prime[i * prime[j]] = 1;
      if (i % prime[j] == 0) {
        mu[i * prime[j]] = 0;
        break;
      } else
        mu[i * prime[j]] = -mu[i];
    }
  }
}
signed main() {
  read(n);
  sieve(n);
  for (int i = 2; i <= n; ++i) {
    if (!d[i])
      for (int j = i; j <= n; j += i)
        if (!d[j]) d[j] = i;
  }
  int p = 1;
  long long ans = (long long)n * n - n + 1;
  for (int d = 1; d <= n; ++d)
    ans -= (long long)mu[d] * (long long)(n / d) * (long long)(n / d);
  for (int i = 1; i <= n; ++i) {
    if (!mu[i]) continue;
    int lim = 0, sum = 0;
    int w = 0;
    for (int j = std::max(i, 2); j <= n; j += i) {
      if (d[j] * 2 > n) continue;
      vis[d[j]]++;
      sum++;
    }
    if (!sum) continue;
    std::vector<std::pair<int, int> > v;
    for (int j = std::max(i, 2); j <= n; j += i) {
      if (d[j] * 2 > n) continue;
      if (vis[d[j]]) {
        v.push_back(std::make_pair(d[j], vis[d[j]]));
        vis[d[j]] = 0;
      }
    }
    std::sort(v.begin(), v.end());
    long long cnt1 = 0, cnt2 = 0;
    int c1 = 0;
    int p = -1;
    for (int j = v.size() - 1; j >= 0; j--) {
      while (p + 1 < v.size() &&
             (long long)v[j].first * (v[p + 1].first) <= n) {
        c1 += v[++p].second;
      }
      cnt1 += (long long)c1 * v[j].second;
      cnt2 += (long long)(sum - c1) * v[j].second;
    }
    v.clear();
    ans += (long long)mu[i] * (2 * cnt1 + 3 * cnt2);
  }
  printf("%lld", ans / 2);
  return 0;
}
template <typename T>
void read(T &x) {
  x = 0;
  char c = getchar();
  T flag = 1;
  while (c < '0' || c > '9') {
    if (c == '-') flag = -flag;
    c = getchar();
  }
  while ('0' <= c && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  x *= flag;
}
template <typename T>
void read(T &x, T &y) {
  read(x);
  read(y);
}
template <typename T>
void read(T &x, T &y, T &z) {
  read(x);
  read(y);
  read(z);
}
template <typename T>
void writeC(T x) {
  if (x < 0) x = ~x + 1, putchar('-');
  if (x > 9) writeC(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
void write(T x) {
  writeC(x);
  putchar(' ');
}
template <typename T>
void writeN(T x) {
  writeC(x);
  puts("");
}
template <typename T>
void _binary(T x, int len) {
  for (int i = len - 1; i >= 0; --i) writeC((x >> i) & 1);
}
long long _inv(long long x, long long M) {
  assert(x != 0);
  return x == 1 ? 1 : (M - M / x) * _inv(M % x, M) % M;
}
long long _qpow(long long a, long long b, long long M) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % M;
    a = a * a % M;
    b >>= 1;
  }
  return res;
}