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 maxn = 1e7 + 1, mod = 1e9 + 7, inf = 1e9;
int n, ted[maxn], ps[maxn], mini[maxn], fi[maxn];
bool aval[maxn];
vector<int> prime;
long long d1, d2, d3;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  prime.push_back(1);
  for (int i = 2; i <= n; i++) {
    if (aval[i] == 0) {
      prime.push_back(i);
      for (int j = i; j <= n; j += i) {
        if (aval[j] == 0) {
          mini[j] = i;
          ted[i]++;
        }
        aval[j] = 1;
      }
    }
  }
  fi[1] = 1;
  for (int i = 2; i <= n; i++) {
    fi[i] = mini[i] - 1;
    int tt = i / mini[i];
    while (tt % mini[i] == 0) {
      tt /= mini[i];
      fi[i] *= mini[i];
    }
    fi[i] *= fi[tt];
    d1 += (i - 1) - fi[i];
  }
  for (int i = 1; i <= n; i++) {
    ps[i] = ps[i - 1] + ted[i];
  }
  for (auto x : prime) {
    if (x != 1) {
      d2 += (1ll * ted[x] * (ted[x] - 1)) / 2;
      int tt = prime[(upper_bound(prime.begin(), prime.end(), n / x) -
                      prime.begin()) -
                     1];
      tt = min(tt, x - 1);
      d2 += 1ll * ted[x] * ps[tt];
      if (x * 2 <= n) {
        d3 += 1ll / ted[x] * (ps[x - 1] - ps[tt]);
      }
    }
  }
  d2 -= d1;
  cout << d1 + d2 * 2 + d3 * 3 << endl;
  return 0;
}