#include <bits/stdc++.h>
#pragma GCC diagnostic ignored "-Wunused-result"
#pragma GCC diagnostic ignored "-Wunused-function"
using namespace std;
namespace {
namespace shik {
template <class T>
void _R(T &x) {
  cin >> x;
}
void _R(int &x) { scanf("%d", &x); }
void _R(int64_t &x) { scanf("%" SCNd64, &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template <class T, class... U>
void R(T &head, U &...tail) {
  _R(head);
  R(tail...);
}
template <class T>
void _W(const T &x) {
  cout << x;
}
void _W(const int &x) { printf("%d", x); }
void _W(const int64_t &x) { printf("%" PRId64, x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template <class T>
void _W(const vector<T> &x) {
  for (auto i = x.begin(); i != x.end(); _W(*i++))
    if (i != x.cbegin()) putchar(' ');
}
void W() {}
template <class T, class... U>
void W(const T &head, const U &...tail) {
  _W(head);
  putchar(sizeof...(tail) ? ' ' : '\n');
  W(tail...);
}
template <class T, class F = less<T>>
void sort_uniq(vector<T> &v, F f = F()) {
  sort(begin(v), end(v), f);
  v.resize(unique(begin(v), end(v)) - begin(v));
}
template <class T>
inline T bit(T x, int i) {
  return (x >> i) & 1;
}
template <class T>
inline bool chkmax(T &a, const T &b) {
  return b > a ? a = b, true : false;
}
template <class T>
inline bool chkmin(T &a, const T &b) {
  return b < a ? a = b, true : false;
}
template <class T>
using MaxHeap = priority_queue<T>;
template <class T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template <class T, typename enable_if<is_integral<T>::value>::type * = nullptr>
constexpr int clz(T x) {
  return sizeof(T) <= sizeof(int) ? __builtin_clz(x) : __builtin_clzll(x);
}
template <class T, typename enable_if<is_integral<T>::value>::type * = nullptr>
constexpr int ctz(T x) {
  return sizeof(T) <= sizeof(int) ? __builtin_ctz(x) : __builtin_ctzll(x);
}
template <class T, typename enable_if<is_integral<T>::value>::type * = nullptr>
constexpr int ffs(T x) {
  return sizeof(T) <= sizeof(int) ? __builtin_ffs(x) : __builtin_ffsll(x);
}
template <class T, typename enable_if<is_integral<T>::value>::type * = nullptr>
constexpr int parity(T x) {
  return sizeof(T) <= sizeof(int) ? __builtin_parity(x) : __builtin_parityll(x);
}
template <class T, typename enable_if<is_integral<T>::value>::type * = nullptr>
constexpr int popcount(T x) {
  return sizeof(T) <= sizeof(int) ? __builtin_popcount(x)
                                  : __builtin_popcountll(x);
}
template <class T>
T has_bit(T x, int i) {
  return (x >> i) & 1;
}
template <class T>
constexpr int lg2(T x) {
  return sizeof(T) * CHAR_BIT - 1 - clz(x);
}
template <class T>
T gcd(T u, T v) {
  if (!u || !v) return u + v;
  int shift = ctz(u | v);
  u >>= ctz(u);
  while (v) {
    v >>= ctz(v);
    if (u > v) swap(u, v);
    v -= u;
  }
  return u << shift;
}
const int N = 1e7 + 10;
int p_tbl[N], mu[N], phi[N];
vector<int> primes;
void sieve() {
  mu[1] = phi[1] = p_tbl[1] = 1;
  for (int i = 2; i < N; i++) {
    if (!p_tbl[i]) {
      primes.push_back(i);
      mu[i] = -1;
      phi[i] = i - 1;
      p_tbl[i] = i;
    }
    for (int p : primes) {
      int x = i * p;
      if (x >= N) break;
      p_tbl[x] = p;
      mu[x] = -mu[i];
      if (i % p == 0) {
        mu[x] = 0;
        phi[x] = phi[i] * p;
        break;
      } else {
        phi[x] = phi[i] * (p - 1);
      }
    }
  }
}
int n;
int dis(int a, int b) {
  if (a == 1 || b == 1) return 0;
  assert(a != b);
  int p = p_tbl[a], q = p_tbl[b];
  bool f1 = (gcd(a, b) > 1);
  bool f2 = (1LL * p * q <= n);
  bool f3 = (2 * max(p, q) <= n);
  assert(f1 <= f2 && f2 <= f3);
  if (f1) return 1;
  if (f2) return 2;
  if (f3) return 3;
  return 0;
}
int64_t solve_1() {
  int64_t ans = 0;
  for (int i = (2); i <= int(n); i++) ans += i - phi[i] - 1;
  ;
  return ans;
}
int cp[N], sp[N];
int64_t solve_2() {
  int64_t ans = 0;
  for (int i = (2); i <= int(n); i++) cp[p_tbl[i]]++;
  for (int i = (2); i <= int(n); i++) sp[i] = sp[i - 1] + cp[i];
  for (int i = 2, j = n; i <= n; i++) {
    if (cp[i] == 0) continue;
    while (i * j > n) j--;
    ans += 1LL * cp[i] * sp[j];
  }
  for (int i = (2); i <= int(n); i++) {
    if (i * i <= n)
      ans -= cp[i];
    else
      break;
  }
  assert(ans % 2 == 0);
  ans /= 2;
  ;
  return ans;
}
int64_t solve_3() {
  int64_t ans = 0;
  for (int i = (2); i <= int(n); i++)
    if (2 * p_tbl[i] <= n) ans++;
  ans = ans * (ans - 1) / 2;
  ;
  return ans;
}
int64_t solve() {
  int64_t ans = 0;
  ans += 3 * solve_3();
  ans -= solve_2();
  ans -= solve_1();
  return ans;
}
int64_t slow() {
  int64_t ans = 0;
  for (int i = (2); i <= int(n); i++)
    for (int j = (i + 1); j <= int(n); j++) {
      int now = dis(i, j);
      ans += now;
    }
  return ans;
}
void main() {
  sieve();
  R(n);
  auto ans = solve();
  W(ans);
}
}  // namespace shik
}  // namespace
int main() {
  shik::main();
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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 GCC diagnostic ignored "-Wunused-result"
#pragma GCC diagnostic ignored "-Wunused-function"
using namespace std;
namespace {
namespace shik {
template <class T>
void _R(T &x) {
  cin >> x;
}
void _R(int &x) { scanf("%d", &x); }
void _R(int64_t &x) { scanf("%" SCNd64, &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template <class T, class... U>
void R(T &head, U &...tail) {
  _R(head);
  R(tail...);
}
template <class T>
void _W(const T &x) {
  cout << x;
}
void _W(const int &x) { printf("%d", x); }
void _W(const int64_t &x) { printf("%" PRId64, x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template <class T>
void _W(const vector<T> &x) {
  for (auto i = x.begin(); i != x.end(); _W(*i++))
    if (i != x.cbegin()) putchar(' ');
}
void W() {}
template <class T, class... U>
void W(const T &head, const U &...tail) {
  _W(head);
  putchar(sizeof...(tail) ? ' ' : '\n');
  W(tail...);
}
template <class T, class F = less<T>>
void sort_uniq(vector<T> &v, F f = F()) {
  sort(begin(v), end(v), f);
  v.resize(unique(begin(v), end(v)) - begin(v));
}
template <class T>
inline T bit(T x, int i) {
  return (x >> i) & 1;
}
template <class T>
inline bool chkmax(T &a, const T &b) {
  return b > a ? a = b, true : false;
}
template <class T>
inline bool chkmin(T &a, const T &b) {
  return b < a ? a = b, true : false;
}
template <class T>
using MaxHeap = priority_queue<T>;
template <class T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template <class T, typename enable_if<is_integral<T>::value>::type * = nullptr>
constexpr int clz(T x) {
  return sizeof(T) <= sizeof(int) ? __builtin_clz(x) : __builtin_clzll(x);
}
template <class T, typename enable_if<is_integral<T>::value>::type * = nullptr>
constexpr int ctz(T x) {
  return sizeof(T) <= sizeof(int) ? __builtin_ctz(x) : __builtin_ctzll(x);
}
template <class T, typename enable_if<is_integral<T>::value>::type * = nullptr>
constexpr int ffs(T x) {
  return sizeof(T) <= sizeof(int) ? __builtin_ffs(x) : __builtin_ffsll(x);
}
template <class T, typename enable_if<is_integral<T>::value>::type * = nullptr>
constexpr int parity(T x) {
  return sizeof(T) <= sizeof(int) ? __builtin_parity(x) : __builtin_parityll(x);
}
template <class T, typename enable_if<is_integral<T>::value>::type * = nullptr>
constexpr int popcount(T x) {
  return sizeof(T) <= sizeof(int) ? __builtin_popcount(x)
                                  : __builtin_popcountll(x);
}
template <class T>
T has_bit(T x, int i) {
  return (x >> i) & 1;
}
template <class T>
constexpr int lg2(T x) {
  return sizeof(T) * CHAR_BIT - 1 - clz(x);
}
template <class T>
T gcd(T u, T v) {
  if (!u || !v) return u + v;
  int shift = ctz(u | v);
  u >>= ctz(u);
  while (v) {
    v >>= ctz(v);
    if (u > v) swap(u, v);
    v -= u;
  }
  return u << shift;
}
const int N = 1e7 + 10;
int p_tbl[N], mu[N], phi[N];
vector<int> primes;
void sieve() {
  mu[1] = phi[1] = p_tbl[1] = 1;
  for (int i = 2; i < N; i++) {
    if (!p_tbl[i]) {
      primes.push_back(i);
      mu[i] = -1;
      phi[i] = i - 1;
      p_tbl[i] = i;
    }
    for (int p : primes) {
      int x = i * p;
      if (x >= N) break;
      p_tbl[x] = p;
      mu[x] = -mu[i];
      if (i % p == 0) {
        mu[x] = 0;
        phi[x] = phi[i] * p;
        break;
      } else {
        phi[x] = phi[i] * (p - 1);
      }
    }
  }
}
int n;
int dis(int a, int b) {
  if (a == 1 || b == 1) return 0;
  assert(a != b);
  int p = p_tbl[a], q = p_tbl[b];
  bool f1 = (gcd(a, b) > 1);
  bool f2 = (1LL * p * q <= n);
  bool f3 = (2 * max(p, q) <= n);
  assert(f1 <= f2 && f2 <= f3);
  if (f1) return 1;
  if (f2) return 2;
  if (f3) return 3;
  return 0;
}
int64_t solve_1() {
  int64_t ans = 0;
  for (int i = (2); i <= int(n); i++) ans += i - phi[i] - 1;
  ;
  return ans;
}
int cp[N], sp[N];
int64_t solve_2() {
  int64_t ans = 0;
  for (int i = (2); i <= int(n); i++) cp[p_tbl[i]]++;
  for (int i = (2); i <= int(n); i++) sp[i] = sp[i - 1] + cp[i];
  for (int i = 2, j = n; i <= n; i++) {
    if (cp[i] == 0) continue;
    while (i * j > n) j--;
    ans += 1LL * cp[i] * sp[j];
  }
  for (int i = (2); i <= int(n); i++) {
    if (i * i <= n)
      ans -= cp[i];
    else
      break;
  }
  assert(ans % 2 == 0);
  ans /= 2;
  ;
  return ans;
}
int64_t solve_3() {
  int64_t ans = 0;
  for (int i = (2); i <= int(n); i++)
    if (2 * p_tbl[i] <= n) ans++;
  ans = ans * (ans - 1) / 2;
  ;
  return ans;
}
int64_t solve() {
  int64_t ans = 0;
  ans += 3 * solve_3();
  ans -= solve_2();
  ans -= solve_1();
  return ans;
}
int64_t slow() {
  int64_t ans = 0;
  for (int i = (2); i <= int(n); i++)
    for (int j = (i + 1); j <= int(n); j++) {
      int now = dis(i, j);
      ans += now;
    }
  return ans;
}
void main() {
  sieve();
  R(n);
  auto ans = solve();
  W(ans);
}
}  // namespace shik
}  // namespace
int main() {
  shik::main();
  return 0;
}

```