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 oo = 2139063143;
const int N = 10010000;
const int P = 1000000007;
const double eps = 1e-7;
template <typename T>
inline void sc(T &x) {
  x = 0;
  static int p;
  p = 1;
  static char c;
  c = getchar();
  while (!isdigit(c)) {
    if (c == '-') p = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c - 48);
    c = getchar();
  }
  x *= p;
}
template <typename T>
inline void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
inline void pr(T x) {
  print(x), putchar('\n');
}
template <typename T1, typename T2>
void chkmax(T1 &A, T2 B) {
  A = A >= B ? A : B;
}
template <typename T1, typename T2>
void chkmin(T1 &A, T2 B) {
  A = A <= B ? A : B;
}
int n;
int pri[N], phi[N], a[N];
bool vis[N];
void init() {
  for (int i = 2; i <= n; i++) {
    if (!vis[i]) pri[++pri[0]] = i, phi[i] = i - 1, ++a[i];
    for (int j = 1; j <= pri[0]; j++) {
      int p = pri[j], k = i * p;
      if (k > n) break;
      vis[k] = 1;
      ++a[p];
      if (i % p == 0) {
        phi[k] = phi[i] * p;
        break;
      }
      phi[k] = phi[i] * (p - 1);
    }
  }
  for (int i = 1; i <= n; i++) a[i] += a[i - 1];
}
int get(int l, int r) { return l > r ? 0 : a[r] - a[l - 1]; }
int main() {
  sc(n);
  init();
  long long s1 = 0;
  for (int i = 2; i <= n; i++) s1 += phi[i] - 1;
  long long ans = (long long)(n - 1) * (n - 2) / 2 + s1;
  for (int i = 1; i <= pri[0]; i++) {
    int p = pri[i], g = a[p] - a[p - 1];
    ans += (long long)g * get(max(p + 1, n / p + 1), max(p + 1, n / 2 + 1) - 1);
    ans -= 2LL * g * get(max(p + 1, n / 2 + 1), n);
  }
  pr(ans);
  return 0;
}