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>
#pragma GCC optimize("Ofast")
using namespace std;
int phi[10000005], p[10000005], num[10000005], n, m;
int f[10000005], g[10000005], pri[10000005 / 10], cnt = 0;
bool isp[10000005];
inline int min(int a, int b) { return a < b ? a : b; }
int main() {
  int i, j;
  scanf("%d", &n);
  phi[1] = 1;
  for (i = 2; i <= n; i++) {
    f[i] = f[i - 1] + (!isp[i]);
    if (!isp[i]) {
      pri[++cnt] = i;
      p[i] = i;
      phi[i] = i - 1;
      g[i] = 1;
      num[i]++;
      m += (i <= n / 2);
    }
    m += (isp[i]);
    for (j = 1; j <= cnt && i * pri[j] <= n; j++) {
      isp[i * pri[j]] = 1;
      p[i * pri[j]] = pri[j];
      num[pri[j]]++;
      g[i * pri[j]] = g[i] + 1;
      if (i % pri[j] == 0) {
        phi[i * pri[j]] = phi[i] * pri[j];
        g[i * pri[j]]--;
        break;
      }
      phi[i * pri[j]] = phi[i] * (pri[j] - 1);
    }
  }
  for (i = 1; i <= n; i++) num[i] += num[i - 1];
  long long tot = 1ll * m * (m - 1);
  tot >>= 1ll;
  long long n1 = 0, n2 = 0, n3 = 0;
  for (i = 2; i <= n; i++) {
    if (isp[i]) {
      n1 += (i - 1 - phi[i]);
      n2 += (phi[i] - f[i] + g[i] - 1);
      continue;
    }
    n2 += num[n / i];
    n2 -= (n / i);
    if (i > n / i) n2++;
    n2 -= f[min(i - 1, n / i)];
  }
  n3 = tot - n1 - n2;
  tot = n1 + 2ll * n2 + 3ll * n3;
  printf("%lld\n", tot);
  return 0;
}