#include <bits/stdc++.h>
using namespace std;
int n, i, j, k, x, y, z, m, q, h, r, timer, mx, l;
int a[200500], b[250005], c[200500];
int pre_bits[1500];
int gcd(int a, int b) { return (b == 0 ? a : gcd(b, a % b)); }
int lcm(int a, int b) { return a * b / gcd(a, b); }
const int N = 10000005;
int lp[N + 5];
vector<int> pr;
vector<int> factors;
int prs[N + 5], sumprs[N + 5];
void factorize(int x) {
  int k = 0;
  while (x != 1) {
    factors.push_back(lp[x]);
    int i = lp[x];
    while (x % i == 0) x /= i;
    k++;
  }
}
int main() {
  cin >> n;
  for (int i = 2; i <= N; ++i) {
    if (lp[i] == 0) {
      lp[i] = i;
      pr.push_back(i);
    }
    for (int j = 0; j < (int)pr.size() && pr[j] <= lp[i] && i * pr[j] <= N; ++j)
      lp[i * pr[j]] = pr[j];
  }
  for (int i = 2; i <= n; i++) {
    prs[lp[i]]++;
  }
  for (int i = 2; i <= n; i++) sumprs[i] = sumprs[i - 1] + prs[i];
  long long ans = 0;
  for (int i = 2; i <= n; i++)
    if (!prs[i] || i <= n / 2) {
      factors.clear();
      factorize(i);
      int min_div = lp[i];
      int sz = factors.size();
      int cnt = 0;
      for (int i = 1; i < (1 << sz); i++) {
        int bits_cnt = 0;
        int cur = n;
        for (int j = 0; j < sz; j++)
          if ((i & (1 << j)) != 0) {
            cur /= factors[j];
            bits_cnt++;
          }
        if (bits_cnt & 1)
          cnt += cur;
        else
          cnt -= cur;
      }
      int tot = n - 1;
      int cnt0 = sumprs[n] - sumprs[n / 2];
      int cnt3 = sumprs[n / 2] - sumprs[n / min_div];
      if (prs[i]) {
        if (i >= n / min_div + 1 && i <= n / 2) cnt3--;
      }
      ans += cnt - 1 + cnt3 * 3 + (tot - cnt0 - cnt3 - cnt) * 2;
    }
  cout << ans / 2 << endl;
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int n, i, j, k, x, y, z, m, q, h, r, timer, mx, l;
int a[200500], b[250005], c[200500];
int pre_bits[1500];
int gcd(int a, int b) { return (b == 0 ? a : gcd(b, a % b)); }
int lcm(int a, int b) { return a * b / gcd(a, b); }
const int N = 10000005;
int lp[N + 5];
vector<int> pr;
vector<int> factors;
int prs[N + 5], sumprs[N + 5];
void factorize(int x) {
  int k = 0;
  while (x != 1) {
    factors.push_back(lp[x]);
    int i = lp[x];
    while (x % i == 0) x /= i;
    k++;
  }
}
int main() {
  cin >> n;
  for (int i = 2; i <= N; ++i) {
    if (lp[i] == 0) {
      lp[i] = i;
      pr.push_back(i);
    }
    for (int j = 0; j < (int)pr.size() && pr[j] <= lp[i] && i * pr[j] <= N; ++j)
      lp[i * pr[j]] = pr[j];
  }
  for (int i = 2; i <= n; i++) {
    prs[lp[i]]++;
  }
  for (int i = 2; i <= n; i++) sumprs[i] = sumprs[i - 1] + prs[i];
  long long ans = 0;
  for (int i = 2; i <= n; i++)
    if (!prs[i] || i <= n / 2) {
      factors.clear();
      factorize(i);
      int min_div = lp[i];
      int sz = factors.size();
      int cnt = 0;
      for (int i = 1; i < (1 << sz); i++) {
        int bits_cnt = 0;
        int cur = n;
        for (int j = 0; j < sz; j++)
          if ((i & (1 << j)) != 0) {
            cur /= factors[j];
            bits_cnt++;
          }
        if (bits_cnt & 1)
          cnt += cur;
        else
          cnt -= cur;
      }
      int tot = n - 1;
      int cnt0 = sumprs[n] - sumprs[n / 2];
      int cnt3 = sumprs[n / 2] - sumprs[n / min_div];
      if (prs[i]) {
        if (i >= n / min_div + 1 && i <= n / 2) cnt3--;
      }
      ans += cnt - 1 + cnt3 * 3 + (tot - cnt0 - cnt3 - cnt) * 2;
    }
  cout << ans / 2 << endl;
  return 0;
}

```