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>
int get() {
  char c;
  while (!isdigit(c = getchar()) && c != '-')
    ;
  int s = c == '-' ? -1 : 1, k = ~s ? c - '0' : 0;
  for (; isdigit(c = getchar()); k = k * 10 + c - '0')
    ;
  return s * k;
}
using namespace std;
const int N = 1e7 + 10;
int n, l, r, phi[N], mn[N], pr[N / 10], tot, cnt[N / 10];
long long s, s0, s1, s2, s3;
int main() {
  scanf("%d", &n);
  for (int i = 2; i <= n; ++i) {
    if (!phi[i]) pr[++tot] = i, phi[i] = i - 1, mn[i] = tot;
    for (int j = 1, t; j <= tot && (t = i * pr[j]) <= n; ++j)
      if (mn[t] = j, i % pr[j])
        phi[t] = phi[i] * (pr[j] - 1);
      else {
        phi[t] = phi[i] * pr[j];
        break;
      }
  }
  for (int i = 2; i <= n; ++i) ++cnt[mn[i]];
  l = upper_bound(pr + 1, pr + tot, sqrt(n)) - pr;
  r = upper_bound(pr + 1, pr + tot, n >> 1) - pr - 1;
  s = n * (n - 1ll) >> 1;
  s0 = n - 1;
  for (int i = r + 1; i <= tot; ++i) s0 += n - 2 - (tot - i);
  s1 = s;
  for (int i = 2; i <= n; ++i) s1 -= phi[i];
  s3 = (r - l + 1ll) * (r - l) / 2;
  for (int i = l, j = l, t = 0; i <= r; ++i) {
    while (j > 2 && (long long)pr[j - 1] * pr[i] > n) t += cnt[--j];
    s3 += t;
    for (int k = 3; k * pr[i] <= n; k += 2) s3 -= mn[k] >= j;
  }
  s2 = s - s0 - s1 - s3;
  printf("%I64d", s1 + s2 * 2 + s3 * 3);
  return 0;
}