#include <bits/stdc++.h>
using namespace std;
int i, j;
int sp[10000005], nump[10000005], phi[10000005], cnt;
long long n, prime[10000005], pfxprime[10000005], temp, temp2, ans0, ans1, ans2,
    ans3;
bool isp[10000005];
int main() {
  scanf("%lld", &n);
  memset(isp, true, sizeof(isp));
  sp[1] = 1;
  nump[1] = 0;
  isp[1] = false;
  cnt = 0;
  for (i = 2; i <= n; i++) {
    if (isp[i]) {
      cnt++;
      prime[cnt] = i;
      sp[i] = i;
      nump[i] = 1;
    }
    for (j = 1; j <= cnt; j++) {
      if (prime[j] * ((long long)i) <= n) {
        isp[prime[j] * i] = false;
        sp[prime[j] * i] = prime[j];
        if (sp[i] != prime[j])
          nump[prime[j] * i] = nump[i] + 1;
        else
          nump[prime[j] * i] = nump[i];
      } else
        break;
      if ((i % prime[j]) == 0) break;
    }
  }
  pfxprime[0] = 0;
  pfxprime[1] = 0;
  for (i = 2; i <= n; i++) {
    if (isp[i])
      pfxprime[i] = pfxprime[i - 1] + 1;
    else
      pfxprime[i] = pfxprime[i - 1];
  }
  phi[1] = 1;
  for (i = 2; i <= n; i++) {
    if (sp[i] != sp[i / sp[i]])
      phi[i] = phi[i / sp[i]] * (sp[i] - 1);
    else
      phi[i] = phi[i / sp[i]] * sp[i];
  }
  temp = pfxprime[n] - pfxprime[n / 2] + 1;
  ans0 = temp * (n - temp) + temp * (temp - 1) / 2;
  ans1 = 0;
  for (i = 2; i <= n; i++) {
    ans1 += i - 1 - phi[i];
  }
  ans2 = 0;
  for (i = 2; i <= n; i++) {
    if (!isp[i]) {
      ans2 += phi[i] - pfxprime[i] - 1 + nump[i];
      ans2 += pfxprime[n / sp[i]];
      temp = i;
      while (sp[temp] * sp[i] <= n) {
        if (temp == 1) break;
        ans2--;
        temp2 = sp[temp];
        while (sp[temp] == temp2) temp /= sp[temp];
      }
    }
  }
  temp = 0;
  for (i = 1; i <= cnt; i++) {
    temp += pfxprime[n / prime[i]];
  }
  temp -= pfxprime[(int)(sqrt(n))];
  ans2 += temp / 2;
  ans3 = n * (n - 1) / 2 - ans0 - ans1 - ans2;
  printf("%lld\n", ans1 + ans2 * 2 + ans3 * 3);
  return 0;
}

### Prompt

Please create a solution in Cpp to the following 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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int i, j;
int sp[10000005], nump[10000005], phi[10000005], cnt;
long long n, prime[10000005], pfxprime[10000005], temp, temp2, ans0, ans1, ans2,
    ans3;
bool isp[10000005];
int main() {
  scanf("%lld", &n);
  memset(isp, true, sizeof(isp));
  sp[1] = 1;
  nump[1] = 0;
  isp[1] = false;
  cnt = 0;
  for (i = 2; i <= n; i++) {
    if (isp[i]) {
      cnt++;
      prime[cnt] = i;
      sp[i] = i;
      nump[i] = 1;
    }
    for (j = 1; j <= cnt; j++) {
      if (prime[j] * ((long long)i) <= n) {
        isp[prime[j] * i] = false;
        sp[prime[j] * i] = prime[j];
        if (sp[i] != prime[j])
          nump[prime[j] * i] = nump[i] + 1;
        else
          nump[prime[j] * i] = nump[i];
      } else
        break;
      if ((i % prime[j]) == 0) break;
    }
  }
  pfxprime[0] = 0;
  pfxprime[1] = 0;
  for (i = 2; i <= n; i++) {
    if (isp[i])
      pfxprime[i] = pfxprime[i - 1] + 1;
    else
      pfxprime[i] = pfxprime[i - 1];
  }
  phi[1] = 1;
  for (i = 2; i <= n; i++) {
    if (sp[i] != sp[i / sp[i]])
      phi[i] = phi[i / sp[i]] * (sp[i] - 1);
    else
      phi[i] = phi[i / sp[i]] * sp[i];
  }
  temp = pfxprime[n] - pfxprime[n / 2] + 1;
  ans0 = temp * (n - temp) + temp * (temp - 1) / 2;
  ans1 = 0;
  for (i = 2; i <= n; i++) {
    ans1 += i - 1 - phi[i];
  }
  ans2 = 0;
  for (i = 2; i <= n; i++) {
    if (!isp[i]) {
      ans2 += phi[i] - pfxprime[i] - 1 + nump[i];
      ans2 += pfxprime[n / sp[i]];
      temp = i;
      while (sp[temp] * sp[i] <= n) {
        if (temp == 1) break;
        ans2--;
        temp2 = sp[temp];
        while (sp[temp] == temp2) temp /= sp[temp];
      }
    }
  }
  temp = 0;
  for (i = 1; i <= cnt; i++) {
    temp += pfxprime[n / prime[i]];
  }
  temp -= pfxprime[(int)(sqrt(n))];
  ans2 += temp / 2;
  ans3 = n * (n - 1) / 2 - ans0 - ans1 - ans2;
  printf("%lld\n", ans1 + ans2 * 2 + ans3 * 3);
  return 0;
}

```