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 gi() {
  int res = 0, w = 1;
  char ch = getchar();
  while (ch != '-' && !isdigit(ch)) ch = getchar();
  if (ch == '-') w = -1, ch = getchar();
  while (isdigit(ch)) res = res * 10 + ch - '0', ch = getchar();
  return res * w;
}
using LL = long long;
const int MAX_N = 1e7 + 5;
int N, mu[MAX_N], prime[MAX_N], mnp[MAX_N], num, buc[MAX_N];
bool nprime[MAX_N];
void sieve() {
  mu[1] = 1;
  for (int i = 2; i <= N; i++) {
    if (!nprime[i]) prime[++num] = i, mnp[i] = i, mu[i] = -1;
    for (int j = 1; j <= num && i * prime[j] <= N; j++) {
      nprime[i * prime[j]] = 1;
      if (i % prime[j] == 0) {
        mnp[i * prime[j]] = mnp[i];
        break;
      } else
        mnp[i * prime[j]] = prime[j], mu[i * prime[j]] = -mu[i];
    }
  }
  for (int i = 1; i <= N; i++) mu[i] += mu[i - 1];
}
int main() {
  cin >> N;
  sieve();
  LL a1 = 0, a2 = 0, a3 = 0, a0 = 0;
  for (int l = 1, r; l <= N; l = r + 1)
    r = N / (N / l), a1 += 1ll * (mu[r] - mu[l - 1]) * (N / l) * (N / l);
  a1 = (1ll * N * N - a1 - N + 1) / 2;
  for (int i = 2; i <= N; i++) buc[mnp[i]]++;
  for (int i = 2; i <= N; i++) buc[i] += buc[i - 1];
  for (int i = 1; i <= num; i++) {
    int now = buc[prime[i]] - buc[prime[i] - 1];
    if (prime[i] <= N / 2)
      a3 += 1ll * now * (buc[N / 2] - buc[max(N / prime[i], prime[i])]);
    a0 += 1ll * now * (buc[N] - buc[max(N / 2, prime[i])]);
  }
  a2 = 1ll * (N - 1) * (N - 2) / 2 - a1 - a0 - a3;
  LL ans = a1 + a3 * 3 + a2 * 2;
  printf("%lld\n", ans);
  return 0;
}