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;
int n, fi[10000005], P[700005], t, f[10000005], x, g[10000005];
long long ans, tmp;
int main() {
  scanf("%d", &n);
  for (int i = 2; i <= n; ++i) {
    if (!f[i]) f[i] = P[++t] = i, fi[i] = i - 1;
    for (int j = 1; j <= t; ++j) {
      x = P[j] * i;
      if (x > n) break;
      f[x] = P[j];
      if (i % P[j])
        fi[x] = fi[i] * (P[j] - 1);
      else {
        fi[x] = fi[i] * P[j];
        break;
      }
    }
  }
  for (int i = 2; i <= n; ++i) ++g[f[i]];
  for (int i = 1; i <= n; ++i) g[i] += g[i - 1];
  for (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 (int i = 2; i <= n; ++i)
    if (1ll * f[i] * f[i] <= n)
      --ans;
    else if (f[i] <= n / 2)
      --tmp;
  for (int i = 2; i <= n; ++i) ans -= i - fi[i] - 1;
  printf("%lld\n", tmp / 2 * 3 + ans);
  return 0;
}