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 MAXN = 10000007;
template <typename T>
inline void read(T &AKNOI) {
  T x = 0, flag = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') flag = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  AKNOI = flag * x;
}
int n, half;
int pr[MAXN], pcnt, vis[MAXN], phi[MAXN];
int low[MAXN], cnt[MAXN];
void sieve() {
  phi[1] = 1;
  for (int i = 2; i <= n; ++i) {
    if (!vis[i]) {
      pr[++pcnt] = i;
      phi[i] = i - 1;
      low[i] = pcnt;
    }
    ++cnt[low[i]];
    for (int j = 1; j <= pcnt; ++j) {
      int k = i * pr[j];
      if (k > n) break;
      vis[k] = 1;
      low[k] = j;
      if (i % pr[j]) {
        phi[k] = phi[i] * (pr[j] - 1);
      } else {
        phi[k] = phi[i] * pr[j];
        break;
      }
    }
  }
  while (pr[pcnt] > half) --pcnt;
  for (int i = pcnt - 1; i >= 1; --i) {
    cnt[i] += cnt[i + 1];
  }
}
void solve() {
  read(n);
  half = n / 2;
  sieve();
  long long ans = 0, g1 = 0, ban = 0;
  for (int i = 2; i <= n; ++i) {
    if (!vis[i] && i > half) {
      ++ban;
    } else {
      ans += i - 1 - phi[i];
      g1 += phi[i] - 1 - ban;
    }
  }
  ans += g1 * 2;
  long long t3 = 0;
  int rt = sqrt(n), pt = pcnt, c = 0;
  for (int i = 1; i <= pcnt; ++i) {
    if (pr[i] <= rt) continue;
    ++c;
    while (1ll * pr[i] * pr[pt - 1] > n) --pt;
    t3 += cnt[pt];
  }
  ans += t3 - 1LL * c * (c + 1) / 2;
  printf("%lld\n", ans);
}
int main() {
  solve();
  return 0;
}