#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline bool chkmin(T &x, T y) {
  return y < x ? x = y, 1 : 0;
}
template <typename T>
inline bool chkmax(T &x, T y) {
  return x < y ? x = y, 1 : 0;
}
const int INF = 0x3f3f3f3f;
const int N = 1e7 + 10;
int phi[N], prime[N], Min[N], sum[N];
int pcnt = 0;
bitset<N> vis;
inline int read() {
  int x = 0, flag = 1;
  char ch = getchar();
  while (!isdigit(ch) && ch != '-') ch = getchar();
  if (ch == '-') flag = -1, ch = getchar();
  while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch - '0'), ch = getchar();
  return x * flag;
}
inline void init(int n) {
  phi[1] = 1;
  for (int i = (2), iend = (n); i <= iend; i++) {
    if (!vis[i]) prime[++pcnt] = i, phi[i] = i - 1, sum[Min[i] = i]++;
    for (int j = 1; j <= pcnt && i * prime[j] <= n; j++) {
      vis[i * prime[j]] = true;
      phi[i * prime[j]] = phi[i] * (prime[j] - 1);
      sum[Min[i * prime[j]] = min(Min[i], prime[j])]++;
      if (i % prime[j] == 0) {
        phi[i * prime[j]] = phi[i] * prime[j];
        break;
      }
    }
  }
}
int main() {
  int n = read();
  long long cnt = 1;
  if (n == 1) return puts("0"), 0;
  init(n);
  long long ans0 = 0, ans1 = 0, ans2 = 0, ans3 = 0;
  for (int i = (n / 2 + 1), iend = (n); i <= iend; i++) cnt += !vis[i];
  ans0 = 1ll * cnt * (n - 1) - 1ll * cnt * (cnt - 1) / 2, cnt = 0;
  for (int i = (2), iend = (n); i <= iend; i++) cnt += phi[i];
  ans1 = 1ll * n * (n - 1) / 2 - cnt, cnt = 0;
  for (int i = (n), iend = (1); i >= iend; i--) sum[i] += sum[i + 1];
  cnt += (n - 1);
  for (int i = (1), iend = (pcnt); i <= iend; i++) cnt += sum[n / prime[i] + 1];
  for (int i = (1), iend = (n); i <= iend; i++) sum[i] = sum[i + 1] + !vis[i];
  for (int i = (1), iend = (pcnt); i <= iend; i++)
    cnt -= sum[max(n / prime[i] + 1, prime[i])];
  ans2 = 1ll * n * (n - 1) / 2 - ans1 - cnt;
  ans3 = 1ll * n * (n - 1) / 2 - ans0 - ans1 - ans2;
  printf("%lld\n", ans1 + 2 * ans2 + 3 * ans3);
  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;
template <typename T>
inline bool chkmin(T &x, T y) {
  return y < x ? x = y, 1 : 0;
}
template <typename T>
inline bool chkmax(T &x, T y) {
  return x < y ? x = y, 1 : 0;
}
const int INF = 0x3f3f3f3f;
const int N = 1e7 + 10;
int phi[N], prime[N], Min[N], sum[N];
int pcnt = 0;
bitset<N> vis;
inline int read() {
  int x = 0, flag = 1;
  char ch = getchar();
  while (!isdigit(ch) && ch != '-') ch = getchar();
  if (ch == '-') flag = -1, ch = getchar();
  while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch - '0'), ch = getchar();
  return x * flag;
}
inline void init(int n) {
  phi[1] = 1;
  for (int i = (2), iend = (n); i <= iend; i++) {
    if (!vis[i]) prime[++pcnt] = i, phi[i] = i - 1, sum[Min[i] = i]++;
    for (int j = 1; j <= pcnt && i * prime[j] <= n; j++) {
      vis[i * prime[j]] = true;
      phi[i * prime[j]] = phi[i] * (prime[j] - 1);
      sum[Min[i * prime[j]] = min(Min[i], prime[j])]++;
      if (i % prime[j] == 0) {
        phi[i * prime[j]] = phi[i] * prime[j];
        break;
      }
    }
  }
}
int main() {
  int n = read();
  long long cnt = 1;
  if (n == 1) return puts("0"), 0;
  init(n);
  long long ans0 = 0, ans1 = 0, ans2 = 0, ans3 = 0;
  for (int i = (n / 2 + 1), iend = (n); i <= iend; i++) cnt += !vis[i];
  ans0 = 1ll * cnt * (n - 1) - 1ll * cnt * (cnt - 1) / 2, cnt = 0;
  for (int i = (2), iend = (n); i <= iend; i++) cnt += phi[i];
  ans1 = 1ll * n * (n - 1) / 2 - cnt, cnt = 0;
  for (int i = (n), iend = (1); i >= iend; i--) sum[i] += sum[i + 1];
  cnt += (n - 1);
  for (int i = (1), iend = (pcnt); i <= iend; i++) cnt += sum[n / prime[i] + 1];
  for (int i = (1), iend = (n); i <= iend; i++) sum[i] = sum[i + 1] + !vis[i];
  for (int i = (1), iend = (pcnt); i <= iend; i++)
    cnt -= sum[max(n / prime[i] + 1, prime[i])];
  ans2 = 1ll * n * (n - 1) / 2 - ans1 - cnt;
  ans3 = 1ll * n * (n - 1) / 2 - ans0 - ans1 - ans2;
  printf("%lld\n", ans1 + 2 * ans2 + 3 * ans3);
  return 0;
}

```