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;
long long n, i, j, ans, tot, s, cnt, m;
int vis[10000005], k, phi[10000005], p[2000005], mn[10000005], c[10000005],
    y[10000005];
int main() {
  cin >> n;
  phi[1] = 1;
  for (i = 2; i <= n; ++i) {
    if (vis[i] == 0) {
      p[++k] = i;
      mn[i] = 1;
      phi[i] = i - 1;
      ++c[i];
      y[i] = i;
    }
    for (j = 1; j <= k && i * p[j] <= n; ++j) {
      int t = i * p[j];
      y[t] = p[j];
      ++c[p[j]];
      vis[t] = 1;
      if (i % p[j] == 0)
        mn[t] = mn[i];
      else
        mn[t] = i;
      if (mn[t] == 1)
        phi[t] = phi[t / p[j]] * p[j];
      else
        phi[t] = phi[mn[t]] * phi[t / mn[t]];
      if (i % p[j] == 0) break;
    }
  }
  tot = n - 1;
  for (i = 2; i <= n; ++i) {
    c[i] += c[i - 1];
    if (vis[i] == 0 && i > n / 2) {
      --tot;
      ++m;
    } else
      ans += phi[i] - 1 - m;
  }
  for (i = 2; i <= n / 2; ++i)
    if (!vis[i]) {
      cnt += c[n / 2] - c[n / i];
      if (i * i > n)
        for (j = i; j <= n; j += i)
          if (y[j] * i > n) --cnt;
    }
  for (i = 2; i <= n; ++i) c[i] = c[i - 1] + (vis[i] == 0);
  for (i = 2; i <= n / 2; ++i)
    if (!vis[i]) cnt -= c[n / 2] - c[max(n / i, i)];
  cout << (tot * (tot - 1) / 2 - ans) + (ans - cnt) * 2 + cnt * 3 << endl;
}