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 N, m[10000001], pr[10000001], u[10000001], v, count[5000001], scn[5000002];
long long O;
int gcd(int a, int b) {
  int r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
int main() {
  scanf("%d", &N);
  u[1] = 1;
  for (int i = 2; i <= N; i++) {
    if (!m[i]) {
      m[i] = pr[++v] = i;
      u[i] = -1;
    }
    for (int j = 1; j <= v && pr[j] * i <= N && pr[j] <= m[i]; j++) {
      m[pr[j] * i] = pr[j];
      u[pr[j] * i] = pr[j] == m[i] ? 0 : -u[i];
    }
  }
  int U = 0;
  for (int i = 2; i <= N; i++)
    if (m[i] << 1 <= N) U++;
  O = (long long)U * (U - 1);
  for (int g = 2; g <= N >> 1; g++)
    O += (long long)(N / g) * (N / g - 1) / 2 * u[g];
  for (int i = 2; i <= N; i++)
    if (m[i] << 1 <= N) count[m[i]]++;
  for (int i = N >> 1; i; i--) scn[i] = scn[i + 1] + count[i];
  int i = 2;
  for (; i * i <= N; i++) O += (long long)count[i] * scn[N / i + 1];
  O += (long long)scn[i] * (scn[i] - 1) / 2;
  printf("%lld\n", O);
  return 0;
}