#include <bits/stdc++.h>
using namespace std;
template <class T>
ostream& operator<<(ostream& stream, const vector<T> v) {
  stream << "[";
  for (int i = 0; i < (int)v.size(); i++) cout << v[i] << " ";
  stream << "]";
  return stream;
}
long long fpow(long long x, long long p, long long m) {
  long long r = 1;
  for (; p >>= 1;) {
    if (p & 1) r = r * x % m;
    x = x * x % m;
  }
  return r;
}
int gcd(int a, int b) {
  if (!b) return a;
  return gcd(b, a % b);
}
long long gcd(long long a, long long b) {
  if (!b) return a;
  return gcd(b, a % b);
}
const int maxn = 10000000;
int N, pi[maxn + 10], sp[maxn + 10], cnt[maxn + 10];
bool v[maxn + 10];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> N;
  long long res = 0, t = 0, bad = 0;
  int i, j;
  for (i = 2; i <= N; i++) {
    if (!v[i]) {
      if (2 * i > N) {
        bad++;
        continue;
      }
      pi[i] = i - 1;
      sp[i] = i;
      for (j = 2 * i; j <= N; j += i) {
        v[j] = 1;
        if (pi[j] == 0) pi[j] = j, sp[j] = i;
        pi[j] = pi[j] / i * (i - 1);
      }
    }
    t++;
    res += pi[i] - 1 - bad;
    cnt[sp[i]]++;
    res += t - 1;
  }
  int l = N + 1;
  long long ct = 0;
  for (i = 2; i <= N; i++)
    if (!v[i] && 2 * i <= N) {
      while (1LL * i * (l - 1) > N && l > i) {
        l--;
        ct += cnt[l];
      }
      while (l < i) {
        ct -= cnt[l];
        l++;
      }
      long long val;
      if (l == i)
        val = 1LL * cnt[i] * (ct - cnt[i]) + 1LL * cnt[i] * (cnt[i] - 1) / 2;
      else
        val = 1LL * cnt[i] * ct;
      res += val;
    }
  cout << res << "\n";
  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 <class T>
ostream& operator<<(ostream& stream, const vector<T> v) {
  stream << "[";
  for (int i = 0; i < (int)v.size(); i++) cout << v[i] << " ";
  stream << "]";
  return stream;
}
long long fpow(long long x, long long p, long long m) {
  long long r = 1;
  for (; p >>= 1;) {
    if (p & 1) r = r * x % m;
    x = x * x % m;
  }
  return r;
}
int gcd(int a, int b) {
  if (!b) return a;
  return gcd(b, a % b);
}
long long gcd(long long a, long long b) {
  if (!b) return a;
  return gcd(b, a % b);
}
const int maxn = 10000000;
int N, pi[maxn + 10], sp[maxn + 10], cnt[maxn + 10];
bool v[maxn + 10];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> N;
  long long res = 0, t = 0, bad = 0;
  int i, j;
  for (i = 2; i <= N; i++) {
    if (!v[i]) {
      if (2 * i > N) {
        bad++;
        continue;
      }
      pi[i] = i - 1;
      sp[i] = i;
      for (j = 2 * i; j <= N; j += i) {
        v[j] = 1;
        if (pi[j] == 0) pi[j] = j, sp[j] = i;
        pi[j] = pi[j] / i * (i - 1);
      }
    }
    t++;
    res += pi[i] - 1 - bad;
    cnt[sp[i]]++;
    res += t - 1;
  }
  int l = N + 1;
  long long ct = 0;
  for (i = 2; i <= N; i++)
    if (!v[i] && 2 * i <= N) {
      while (1LL * i * (l - 1) > N && l > i) {
        l--;
        ct += cnt[l];
      }
      while (l < i) {
        ct -= cnt[l];
        l++;
      }
      long long val;
      if (l == i)
        val = 1LL * cnt[i] * (ct - cnt[i]) + 1LL * cnt[i] * (cnt[i] - 1) / 2;
      else
        val = 1LL * cnt[i] * ct;
      res += val;
    }
  cout << res << "\n";
  return 0;
}

```