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 main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> pri;
  vector<int> phi(n + 5);
  unordered_map<int, bool> mp;
  vector<int> pre(n + 5);
  vector<int> mark(n + 5);
  int tot;
  auto Phi = [&](int k) {
    phi[1] = 1;
    for (int i = 2; i <= k; ++i) {
      if (!phi[i]) {
        phi[i] = i - 1;
        pri.emplace_back(i);
        mp[i] = 1;
        mark[i] = (int)pri.size();
      }
      int pos = 0;
      for (auto x : pri) {
        pos++;
        if (i * x > n) break;
        mark[i * x] = pos;
        if (i % x == 0) {
          phi[i * x] = phi[i] * x;
          break;
        } else {
          phi[i * x] = phi[i] * phi[x];
        }
      }
    }
    tot = (int)pri.size();
    if (tot) {
      for (int i = 2; i <= k; ++i) {
        pre[mark[i]]++;
      }
      while (pri[tot - 1] > n / 2) tot--;
      for (int i = tot - 1; i >= 1; --i) {
        pre[i] += pre[i + 1];
      }
    }
  };
  Phi(n);
  long long ans = 0, res = 0;
  int cnt = 0;
  for (int i = 2; i <= n; ++i) {
    ans += i - 1 - phi[i];
    if (i <= n / 2 || !mp[i])
      res += phi[i] - 1 - cnt;
    else
      cnt++;
  }
  ans += 2 * res;
  res = 0;
  int max_lim = sqrt(n), cnr = tot, sum = 0;
  for (int i = 1; i <= tot; ++i) {
    if (pri[i - 1] <= max_lim) continue;
    while (1ll * pri[cnr - 2] * pri[i - 1] > n) cnr--;
    res += pre[cnr];
    sum++;
  }
  res -= 1ll * sum * (sum + 1) / 2;
  ans += res;
  cout << ans << '\n';
  return 0;
}