#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e7 + 7;
const int INF = 0x3F3F3F3F;
int sf[MAX], phi[MAX], bit[MAX];
vector<int> primes;
void sieve() {
  phi[1] = 1;
  for (int i = 2; i < MAX; ++i) {
    if (sf[i] == 0) {
      sf[i] = i;
      phi[i] = i - 1;
      primes.push_back(i);
    } else {
      if (sf[i] == sf[i / sf[i]]) {
        phi[i] = phi[i / sf[i]] * sf[i];
      } else {
        phi[i] = phi[i / sf[i]] * (sf[i] - 1);
      }
    }
    for (long long j = 0;
         j < (int)primes.size() && primes[j] <= sf[i] && i * primes[j] < MAX;
         j++) {
      sf[i * primes[j]] = primes[j];
    }
  }
}
void update(int idx) {
  while (idx < MAX) {
    bit[idx]++;
    idx += idx & -idx;
  }
}
int query(int idx) {
  int sum = 0;
  while (idx) {
    sum += bit[idx];
    idx -= idx & -idx;
  }
  return sum;
}
int main() {
  sieve();
  int n;
  scanf("%d", &n);
  int type3 = 0;
  long long ans = 0;
  for (int i = int(2); i < int(n + 1); i++) {
    int d1 = (i - 1) - phi[i], d2 = 0, d3 = 0;
    d2 = query(n / sf[i]) - d1;
    update(sf[i]);
    if (2 * sf[i] <= n) {
      d3 = type3 - d1 - d2;
      type3++;
    }
    ans += d1 + 2 * d2 + 3 * d3;
  }
  printf("%lld\n", ans);
  return 0;
}

### Prompt

Your challenge is to write a cpp solution 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;
const int MAX = 1e7 + 7;
const int INF = 0x3F3F3F3F;
int sf[MAX], phi[MAX], bit[MAX];
vector<int> primes;
void sieve() {
  phi[1] = 1;
  for (int i = 2; i < MAX; ++i) {
    if (sf[i] == 0) {
      sf[i] = i;
      phi[i] = i - 1;
      primes.push_back(i);
    } else {
      if (sf[i] == sf[i / sf[i]]) {
        phi[i] = phi[i / sf[i]] * sf[i];
      } else {
        phi[i] = phi[i / sf[i]] * (sf[i] - 1);
      }
    }
    for (long long j = 0;
         j < (int)primes.size() && primes[j] <= sf[i] && i * primes[j] < MAX;
         j++) {
      sf[i * primes[j]] = primes[j];
    }
  }
}
void update(int idx) {
  while (idx < MAX) {
    bit[idx]++;
    idx += idx & -idx;
  }
}
int query(int idx) {
  int sum = 0;
  while (idx) {
    sum += bit[idx];
    idx -= idx & -idx;
  }
  return sum;
}
int main() {
  sieve();
  int n;
  scanf("%d", &n);
  int type3 = 0;
  long long ans = 0;
  for (int i = int(2); i < int(n + 1); i++) {
    int d1 = (i - 1) - phi[i], d2 = 0, d3 = 0;
    d2 = query(n / sf[i]) - d1;
    update(sf[i]);
    if (2 * sf[i] <= n) {
      d3 = type3 - d1 - d2;
      type3++;
    }
    ans += d1 + 2 * d2 + 3 * d3;
  }
  printf("%lld\n", ans);
  return 0;
}

```