#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10000010;
int _w;
int n;
namespace Prelude {
bool isp[MAXN];
int prm[MAXN], pcnt;
int phi[MAXN];
int upc[MAXN];
int smallp[MAXN];
void solve() {
  memset(isp, 1, sizeof isp);
  isp[0] = isp[1] = 0;
  for (int i = 2; i <= n; ++i) {
    if (isp[i]) {
      prm[pcnt++] = i;
      phi[i] = i - 1;
      upc[i] = 1;
      smallp[i] = i;
    }
    for (int j = 0; j < pcnt; ++j) {
      int k = i * prm[j];
      if (k > n) break;
      isp[k] = 0;
      smallp[k] = prm[j];
      if (i % prm[j]) {
        phi[k] = phi[i] * phi[prm[j]];
        upc[k] = upc[i] + 1;
      } else {
        phi[k] = phi[i] * prm[j];
        upc[k] = upc[i];
        break;
      }
    }
  }
}
}  // namespace Prelude
using namespace Prelude;
namespace Solve0 {
long long solve() {
  int g = n - 1;
  for (int i = n; i > n / 2; --i)
    if (isp[i]) --g;
  return (long long)n * (n - 1) / 2 - (long long)g * (g - 1) / 2;
}
}  // namespace Solve0
namespace Solve1 {
long long solve() {
  long long ans = 0;
  for (int i = 1; i <= n; ++i) ans += i - phi[i] - 1;
  return ans;
}
}  // namespace Solve1
namespace Solve2 {
long long part1() {
  long long ans = 0;
  int sump = 1;
  for (int i = 2; i <= n; ++i) {
    if (!isp[i]) ans += phi[i] - sump + upc[i];
    sump += isp[i];
  }
  return ans;
}
int ssp[MAXN];
long long part2() {
  for (int i = 2; i <= n; ++i)
    if (!(i > n / 2 && isp[i])) ++ssp[smallp[i]];
  for (int i = 3; i <= n; ++i) ssp[i] += ssp[i - 1];
  long long ans = 0;
  for (int i = 2; i <= n / 2; ++i)
    if (isp[i]) {
      ans += ssp[n / i];
      for (int j = i; j <= n; j += i)
        if (smallp[j] <= n / i) --ans;
    }
  return ans;
}
int spc[MAXN];
long long part3() {
  for (int i = 2; i <= n / 2; ++i) spc[i] = spc[i - 1] + isp[i];
  long long ans = 0;
  int sump = 0;
  for (int i = 2; i <= n / 2; ++i)
    if (isp[i]) ans += min(spc[n / i], sump++);
  return ans;
}
long long solve() { return part1() + part2() - part3(); }
}  // namespace Solve2
namespace Solve {
void solve() {
  long long ans = 0, tot = (long long)n * (n - 1) / 2;
  tot -= Solve0::solve();
  long long c1 = Solve1::solve();
  ans += c1, tot -= c1;
  ans += tot * 3 - Solve2::solve();
  printf("%lld\n", ans);
}
}  // namespace Solve
int main() {
  _w = scanf("%d", &n);
  Prelude::solve();
  Solve::solve();
  return 0;
}

### Prompt

In cpp, your task is to solve 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;
const int MAXN = 10000010;
int _w;
int n;
namespace Prelude {
bool isp[MAXN];
int prm[MAXN], pcnt;
int phi[MAXN];
int upc[MAXN];
int smallp[MAXN];
void solve() {
  memset(isp, 1, sizeof isp);
  isp[0] = isp[1] = 0;
  for (int i = 2; i <= n; ++i) {
    if (isp[i]) {
      prm[pcnt++] = i;
      phi[i] = i - 1;
      upc[i] = 1;
      smallp[i] = i;
    }
    for (int j = 0; j < pcnt; ++j) {
      int k = i * prm[j];
      if (k > n) break;
      isp[k] = 0;
      smallp[k] = prm[j];
      if (i % prm[j]) {
        phi[k] = phi[i] * phi[prm[j]];
        upc[k] = upc[i] + 1;
      } else {
        phi[k] = phi[i] * prm[j];
        upc[k] = upc[i];
        break;
      }
    }
  }
}
}  // namespace Prelude
using namespace Prelude;
namespace Solve0 {
long long solve() {
  int g = n - 1;
  for (int i = n; i > n / 2; --i)
    if (isp[i]) --g;
  return (long long)n * (n - 1) / 2 - (long long)g * (g - 1) / 2;
}
}  // namespace Solve0
namespace Solve1 {
long long solve() {
  long long ans = 0;
  for (int i = 1; i <= n; ++i) ans += i - phi[i] - 1;
  return ans;
}
}  // namespace Solve1
namespace Solve2 {
long long part1() {
  long long ans = 0;
  int sump = 1;
  for (int i = 2; i <= n; ++i) {
    if (!isp[i]) ans += phi[i] - sump + upc[i];
    sump += isp[i];
  }
  return ans;
}
int ssp[MAXN];
long long part2() {
  for (int i = 2; i <= n; ++i)
    if (!(i > n / 2 && isp[i])) ++ssp[smallp[i]];
  for (int i = 3; i <= n; ++i) ssp[i] += ssp[i - 1];
  long long ans = 0;
  for (int i = 2; i <= n / 2; ++i)
    if (isp[i]) {
      ans += ssp[n / i];
      for (int j = i; j <= n; j += i)
        if (smallp[j] <= n / i) --ans;
    }
  return ans;
}
int spc[MAXN];
long long part3() {
  for (int i = 2; i <= n / 2; ++i) spc[i] = spc[i - 1] + isp[i];
  long long ans = 0;
  int sump = 0;
  for (int i = 2; i <= n / 2; ++i)
    if (isp[i]) ans += min(spc[n / i], sump++);
  return ans;
}
long long solve() { return part1() + part2() - part3(); }
}  // namespace Solve2
namespace Solve {
void solve() {
  long long ans = 0, tot = (long long)n * (n - 1) / 2;
  tot -= Solve0::solve();
  long long c1 = Solve1::solve();
  ans += c1, tot -= c1;
  ans += tot * 3 - Solve2::solve();
  printf("%lld\n", ans);
}
}  // namespace Solve
int main() {
  _w = scanf("%d", &n);
  Prelude::solve();
  Solve::solve();
  return 0;
}

```