#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using uint = unsigned int;
template <class T>
using V = vector<T>;
template <class T>
using VV = vector<vector<T>>;
template <class T, class U>
void chmax(T& x, U y) {
  if (x < y) x = y;
}
template <class T, class U>
void chmin(T& x, U y) {
  if (y < x) x = y;
}
template <class T>
void mkuni(V<T>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
}
template <class S, class T>
ostream& operator<<(ostream& o, const pair<S, T>& p) {
  return o << "(" << p.first << "," << p.second << ")";
}
template <class T>
ostream& operator<<(ostream& o, const vector<T>& vc) {
  o << "{";
  for (const T& v : vc) o << v << ",";
  o << "}";
  return o;
}
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  ll N;
  cin >> N;
  V<int> f(N + 1, -1);
  V<int> meb(N + 1, 1);
  V<bool> survive(N + 1);
  {
    V<int> v(N + 1);
    for (int i = 1; i <= int(N); i++) v[i] = i;
    for (int i = 2; i <= N; i++)
      if (f[i] == -1) {
        for (int x = i; x <= N; x += i) {
          if (f[x] == -1) f[x] = i;
          v[x] /= i;
          meb[x] = -meb[x];
        }
      }
    for (int i = 1; i <= int(N); i++)
      if (v[i] > 1) meb[i] = 0;
  }
  for (int i = 2; i <= N; i++) {
    survive[i] = !(f[i] == i && i > N / 2);
  }
  ll A = 0, B = 0;
  V<ll> buf(10000010);
  for (int d = 1; d <= N; d++)
    if (meb[d] != 0) {
      ll a = 0, b = 0;
      for (int x = d; x <= N; x += d)
        if (survive[x]) {
          a++;
        }
      a *= a;
      if (d > 1 && ll(f[d]) * f[d] <= N) {
        b = a;
      } else {
        int I = 0;
        for (int x = d; x <= N; x += d)
          if (survive[x]) {
            buf[I++] = f[x];
          }
        sort(buf.begin(), buf.begin() + I);
        int j = I - 1;
        for (int i = 0; i < int(I); i++) {
          while (j >= 0 && buf[i] * buf[j] > N) j--;
          b += j + 1;
        }
      }
      A += a * meb[d];
      B += b * meb[d];
    }
  for (int i = 1; i <= int(N); i++)
    if (survive[i]) {
      void(0);
    }
  void(0);
  ll cnt = 0;
  for (int i = 1; i <= int(N); i++)
    if (survive[i]) cnt++;
  ll one = cnt * cnt - A;
  ll two = B;
  ll three = A - B;
  one -= cnt;
  ll ans = one + two * 2 + three * 3;
  void(0);
  cout << ans / 2 << endl;
}

### 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>
using namespace std;
using ll = long long;
using uint = unsigned int;
template <class T>
using V = vector<T>;
template <class T>
using VV = vector<vector<T>>;
template <class T, class U>
void chmax(T& x, U y) {
  if (x < y) x = y;
}
template <class T, class U>
void chmin(T& x, U y) {
  if (y < x) x = y;
}
template <class T>
void mkuni(V<T>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
}
template <class S, class T>
ostream& operator<<(ostream& o, const pair<S, T>& p) {
  return o << "(" << p.first << "," << p.second << ")";
}
template <class T>
ostream& operator<<(ostream& o, const vector<T>& vc) {
  o << "{";
  for (const T& v : vc) o << v << ",";
  o << "}";
  return o;
}
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  ll N;
  cin >> N;
  V<int> f(N + 1, -1);
  V<int> meb(N + 1, 1);
  V<bool> survive(N + 1);
  {
    V<int> v(N + 1);
    for (int i = 1; i <= int(N); i++) v[i] = i;
    for (int i = 2; i <= N; i++)
      if (f[i] == -1) {
        for (int x = i; x <= N; x += i) {
          if (f[x] == -1) f[x] = i;
          v[x] /= i;
          meb[x] = -meb[x];
        }
      }
    for (int i = 1; i <= int(N); i++)
      if (v[i] > 1) meb[i] = 0;
  }
  for (int i = 2; i <= N; i++) {
    survive[i] = !(f[i] == i && i > N / 2);
  }
  ll A = 0, B = 0;
  V<ll> buf(10000010);
  for (int d = 1; d <= N; d++)
    if (meb[d] != 0) {
      ll a = 0, b = 0;
      for (int x = d; x <= N; x += d)
        if (survive[x]) {
          a++;
        }
      a *= a;
      if (d > 1 && ll(f[d]) * f[d] <= N) {
        b = a;
      } else {
        int I = 0;
        for (int x = d; x <= N; x += d)
          if (survive[x]) {
            buf[I++] = f[x];
          }
        sort(buf.begin(), buf.begin() + I);
        int j = I - 1;
        for (int i = 0; i < int(I); i++) {
          while (j >= 0 && buf[i] * buf[j] > N) j--;
          b += j + 1;
        }
      }
      A += a * meb[d];
      B += b * meb[d];
    }
  for (int i = 1; i <= int(N); i++)
    if (survive[i]) {
      void(0);
    }
  void(0);
  ll cnt = 0;
  for (int i = 1; i <= int(N); i++)
    if (survive[i]) cnt++;
  ll one = cnt * cnt - A;
  ll two = B;
  ll three = A - B;
  one -= cnt;
  ll ans = one + two * 2 + three * 3;
  void(0);
  cout << ans / 2 << endl;
}

```