#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
const int INF = (int)(1e9 + 1e5);
const long long LINF = (long long)(1e18);
const double EPS = 1e-9;
const int MOD = 1000000007;
const int BASE = 1000003;
const int MAXN = 10000005;
int m;
int d[105][105];
long long ans;
int lp[MAXN];
vector<int> primes;
int fen[MAXN];
void add(int pos) {
  while (pos < MAXN) {
    ++fen[pos];
    pos |= (pos + 1);
  }
}
int get(int pos) {
  int res = 0;
  while (pos > 0) {
    res += fen[pos];
    pos &= (pos + 1);
    --pos;
  }
  return res;
}
void sieve() {
  lp[1] = 1;
  for (int i = 2; i < MAXN; ++i) {
    if (!lp[i]) {
      lp[i] = i;
      primes.push_back(i);
    }
    for (int j = 0; j < (int)primes.size(); ++j) {
      int q = primes[j] * i;
      if (q >= MAXN) {
        break;
      }
      lp[q] = primes[j];
    }
  }
}
int get_phi(int n) {
  int res = n;
  while (n > 1) {
    int p = lp[n];
    res -= res / p;
    while (lp[n] == p) {
      n /= p;
    }
  }
  return res;
}
bool is_good(int n) {
  return lp[n] > 2 && n / lp[n] > 1 && lp[n / lp[n]] == n / lp[n] &&
         lp[n] * lp[n] != n;
}
void solve() {
  sieve();
  scanf("%d", &m);
  int q1 = 0, q2 = -1;
  for (int n = 1; n <= m; ++n) {
    while (q2 + 1 < (int)primes.size() && primes[q2 + 1] <= n) {
      ++q2;
    }
    while (primes[q1] * 2 <= n) {
      ++q1;
    }
    if (is_good(n)) {
      int x = lp[n], y = n / lp[n];
      ans -= get(x) - get(x - 1);
    } else if (n == 4) {
      ans += 1;
    } else if (n > 4 && (n & 1) == 0 && lp[n >> 1] == (n >> 1) &&
               (n >> 1) > 1) {
      int two = (n / 2 - 1);
      ans += two * 2;
      ans += (n - two - 3 - (q2 - q1 + 1)) * 3;
    }
    int cnt_1 = n - get_phi(n) - 1;
    int cnt_3 = get(n / 2) - get(n / lp[n]);
    int cnt_2 = n - 2 - cnt_1 - cnt_3 - (q2 - q1 + 1);
    if (n > 4 && lp[n] != n) {
      ans += cnt_1 + cnt_2 * 2 + cnt_3 * 3;
    }
    add(lp[n]);
  }
  printf("%I64d\n", ans);
}
int main() {
  srand(11);
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int tests = 1;
  for (int test = 1; test <= tests; test++) {
    solve();
  }
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
const int INF = (int)(1e9 + 1e5);
const long long LINF = (long long)(1e18);
const double EPS = 1e-9;
const int MOD = 1000000007;
const int BASE = 1000003;
const int MAXN = 10000005;
int m;
int d[105][105];
long long ans;
int lp[MAXN];
vector<int> primes;
int fen[MAXN];
void add(int pos) {
  while (pos < MAXN) {
    ++fen[pos];
    pos |= (pos + 1);
  }
}
int get(int pos) {
  int res = 0;
  while (pos > 0) {
    res += fen[pos];
    pos &= (pos + 1);
    --pos;
  }
  return res;
}
void sieve() {
  lp[1] = 1;
  for (int i = 2; i < MAXN; ++i) {
    if (!lp[i]) {
      lp[i] = i;
      primes.push_back(i);
    }
    for (int j = 0; j < (int)primes.size(); ++j) {
      int q = primes[j] * i;
      if (q >= MAXN) {
        break;
      }
      lp[q] = primes[j];
    }
  }
}
int get_phi(int n) {
  int res = n;
  while (n > 1) {
    int p = lp[n];
    res -= res / p;
    while (lp[n] == p) {
      n /= p;
    }
  }
  return res;
}
bool is_good(int n) {
  return lp[n] > 2 && n / lp[n] > 1 && lp[n / lp[n]] == n / lp[n] &&
         lp[n] * lp[n] != n;
}
void solve() {
  sieve();
  scanf("%d", &m);
  int q1 = 0, q2 = -1;
  for (int n = 1; n <= m; ++n) {
    while (q2 + 1 < (int)primes.size() && primes[q2 + 1] <= n) {
      ++q2;
    }
    while (primes[q1] * 2 <= n) {
      ++q1;
    }
    if (is_good(n)) {
      int x = lp[n], y = n / lp[n];
      ans -= get(x) - get(x - 1);
    } else if (n == 4) {
      ans += 1;
    } else if (n > 4 && (n & 1) == 0 && lp[n >> 1] == (n >> 1) &&
               (n >> 1) > 1) {
      int two = (n / 2 - 1);
      ans += two * 2;
      ans += (n - two - 3 - (q2 - q1 + 1)) * 3;
    }
    int cnt_1 = n - get_phi(n) - 1;
    int cnt_3 = get(n / 2) - get(n / lp[n]);
    int cnt_2 = n - 2 - cnt_1 - cnt_3 - (q2 - q1 + 1);
    if (n > 4 && lp[n] != n) {
      ans += cnt_1 + cnt_2 * 2 + cnt_3 * 3;
    }
    add(lp[n]);
  }
  printf("%I64d\n", ans);
}
int main() {
  srand(11);
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int tests = 1;
  for (int test = 1; test <= tests; test++) {
    solve();
  }
  return 0;
}

```