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 N = 1e7 + 5;
int v[N], p[N], fi[N], g[N];
long long ans, tmp;
int main() {
  int n, t = 0;
  scanf("%d", &n);
  for (register int i = 2; i <= n; ++i) {
    if (!v[i]) v[i] = p[++t] = i, fi[i] = i - 1;
    for (register int j = 1; j <= t && i * p[j] <= n; ++j) {
      int x = i * p[j];
      v[x] = p[j];
      if (i % p[j])
        fi[x] = fi[i] * (p[j] - 1);
      else {
        fi[x] = fi[i] * p[j];
        break;
      }
    }
  }
  for (register int i = 2; i <= n; ++i) ++g[v[i]];
  for (register int i = 1; i <= n; ++i) g[i] += g[i - 1];
  for (register int i = 1, j = t; i <= t; ++i) {
    while (p[i] * p[j] > n) --j;
    ans += 1ll * (g[p[i]] - g[p[i] - 1]) * g[p[j]];
    if (p[i] <= n / 2)
      tmp += 1ll * (g[p[i]] - g[p[i] - 1]) *
             (n / 2 > p[j] ? g[n / 2] - g[p[j]] : 0);
  }
  for (register int i = 2; i <= n; ++i)
    if (1ll * v[i] * v[i] <= n)
      --ans;
    else if (v[i] <= n / 2)
      --tmp;
  for (register int i = 2; i <= n; ++i) ans -= i - fi[i] - 1;
  printf("%lld\n", tmp / 2 * 3 + ans);
  return 0;
}