#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
const long long INF = 1e18;
int mindiv[10000001];
long long N;
long long gcdnum[10000001];
long long ans = 0;
long long mindivnum[10000001];
long long mindivsum[10000002];
int main() {
  cin >> N;
  vector<long long> primes;
  long long composite = 0;
  for (int i = 1; i <= N; i++) {
    mindiv[i] = -1;
  }
  mindiv[1] = 1;
  for (int i = 2; i <= N; i++) {
    if (mindiv[i] != -1) {
      composite++;
      continue;
    }
    if (i * 2 <= N) primes.push_back(i);
    for (int j = i * 2; j <= N; j += i) {
      if (mindiv[j] == -1) mindiv[j] = i;
    }
  }
  for (int i = 2; i <= N; i++) {
    if (mindiv[i] == -1) continue;
    mindivnum[mindiv[i]]++;
  }
  for (int i = 1; i <= N; i++) {
    mindivsum[i + 1] = mindivsum[i] + mindivnum[i];
  }
  ans = (long long)primes.size() * ((long long)primes.size() - 1) * 2;
  for (int i = 0; i < primes.size(); i++) {
    long long tmp = N / primes[i] + 1;
    auto itr = lower_bound(primes.begin(), primes.end(), tmp);
    long long num = distance(itr, primes.end());
    ans += num;
    if (primes[i] * primes[i] > N) ans--;
  }
  ans /= 2;
  gcdnum[1] = composite * (composite - 1) / 2;
  for (long long i = 2; i <= N; i++) {
    long long num = N / i;
    if (mindiv[i] == -1) num--;
    gcdnum[i] = num * (num - 1) / 2;
  }
  for (long long i = N; i >= 1; i--) {
    for (long long j = i * 2; j <= N; j += i) {
      gcdnum[i] -= gcdnum[j];
    }
  }
  ans += composite * (composite - 1) / 2;
  ans += gcdnum[1];
  for (auto p : primes) {
    ans += 3 * composite;
    long long f = N / p;
    ans -= mindivsum[f + 1];
    ans -= (N / p) - 1;
  }
  cout << ans << "\n";
  return 0;
}

### Prompt

In CPP, your task is to solve 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>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
const long long INF = 1e18;
int mindiv[10000001];
long long N;
long long gcdnum[10000001];
long long ans = 0;
long long mindivnum[10000001];
long long mindivsum[10000002];
int main() {
  cin >> N;
  vector<long long> primes;
  long long composite = 0;
  for (int i = 1; i <= N; i++) {
    mindiv[i] = -1;
  }
  mindiv[1] = 1;
  for (int i = 2; i <= N; i++) {
    if (mindiv[i] != -1) {
      composite++;
      continue;
    }
    if (i * 2 <= N) primes.push_back(i);
    for (int j = i * 2; j <= N; j += i) {
      if (mindiv[j] == -1) mindiv[j] = i;
    }
  }
  for (int i = 2; i <= N; i++) {
    if (mindiv[i] == -1) continue;
    mindivnum[mindiv[i]]++;
  }
  for (int i = 1; i <= N; i++) {
    mindivsum[i + 1] = mindivsum[i] + mindivnum[i];
  }
  ans = (long long)primes.size() * ((long long)primes.size() - 1) * 2;
  for (int i = 0; i < primes.size(); i++) {
    long long tmp = N / primes[i] + 1;
    auto itr = lower_bound(primes.begin(), primes.end(), tmp);
    long long num = distance(itr, primes.end());
    ans += num;
    if (primes[i] * primes[i] > N) ans--;
  }
  ans /= 2;
  gcdnum[1] = composite * (composite - 1) / 2;
  for (long long i = 2; i <= N; i++) {
    long long num = N / i;
    if (mindiv[i] == -1) num--;
    gcdnum[i] = num * (num - 1) / 2;
  }
  for (long long i = N; i >= 1; i--) {
    for (long long j = i * 2; j <= N; j += i) {
      gcdnum[i] -= gcdnum[j];
    }
  }
  ans += composite * (composite - 1) / 2;
  ans += gcdnum[1];
  for (auto p : primes) {
    ans += 3 * composite;
    long long f = N / p;
    ans -= mindivsum[f + 1];
    ans -= (N / p) - 1;
  }
  cout << ans << "\n";
  return 0;
}

```