#include <bits/stdc++.h>
int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);
  int number;
  std::cin >> number;
  std::vector<int> minFactor(number + 1), mob(number + 1, 1);
  for (int prime = 2; prime < (int)minFactor.size(); ++prime)
    if (minFactor[prime] == 0) {
      for (int multiple = prime; multiple < (int)minFactor.size();
           multiple += prime) {
        mob[multiple] *= -1;
        if (minFactor[multiple] == 0) minFactor[multiple] = prime;
        assert(mob[prime] == -1);
      }
      if ((int64_t)prime * prime < (int)minFactor.size())
        for (int multiple = prime * prime; multiple < (int)minFactor.size();
             multiple += prime * prime)
          mob[multiple] = 0;
    }
  std::vector<int> countMinFactor(number / 2 + 1);
  int total{};
  for (int x = 2; x <= number; ++x)
    if (minFactor[x] < (int)countMinFactor.size()) {
      total++;
      countMinFactor[minFactor[x]]++;
    }
  auto const c2 = [&](int64_t it) { return (it * (it - 1)) >> 1; };
  int64_t numPair1{};
  for (int d = 2; d <= number; ++d) numPair1 -= mob[d] * c2(number / d);
  assert(numPair1 >= 0);
  int64_t numPair3{};
  std::vector<int> countMinFactorGE = countMinFactor;
  for (int index = (int)countMinFactorGE.size() - 1; index--;)
    countMinFactorGE[index] += countMinFactorGE[index + 1];
  for (int a = 3; a < (int)countMinFactor.size() - 1; ++a) {
    numPair3 += (int64_t)countMinFactor[a] *
                (countMinFactorGE[std::max(a + 1, number / a + 1)]);
  }
  int64_t numPair2 = c2(total) - numPair1 - numPair3;
  assert(numPair2 >= 0);
  std::cout << 1 * numPair1 + 2 * (c2(total) - numPair1 - numPair3) +
                   3 * numPair3
            << '\n';
}

### 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>
int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);
  int number;
  std::cin >> number;
  std::vector<int> minFactor(number + 1), mob(number + 1, 1);
  for (int prime = 2; prime < (int)minFactor.size(); ++prime)
    if (minFactor[prime] == 0) {
      for (int multiple = prime; multiple < (int)minFactor.size();
           multiple += prime) {
        mob[multiple] *= -1;
        if (minFactor[multiple] == 0) minFactor[multiple] = prime;
        assert(mob[prime] == -1);
      }
      if ((int64_t)prime * prime < (int)minFactor.size())
        for (int multiple = prime * prime; multiple < (int)minFactor.size();
             multiple += prime * prime)
          mob[multiple] = 0;
    }
  std::vector<int> countMinFactor(number / 2 + 1);
  int total{};
  for (int x = 2; x <= number; ++x)
    if (minFactor[x] < (int)countMinFactor.size()) {
      total++;
      countMinFactor[minFactor[x]]++;
    }
  auto const c2 = [&](int64_t it) { return (it * (it - 1)) >> 1; };
  int64_t numPair1{};
  for (int d = 2; d <= number; ++d) numPair1 -= mob[d] * c2(number / d);
  assert(numPair1 >= 0);
  int64_t numPair3{};
  std::vector<int> countMinFactorGE = countMinFactor;
  for (int index = (int)countMinFactorGE.size() - 1; index--;)
    countMinFactorGE[index] += countMinFactorGE[index + 1];
  for (int a = 3; a < (int)countMinFactor.size() - 1; ++a) {
    numPair3 += (int64_t)countMinFactor[a] *
                (countMinFactorGE[std::max(a + 1, number / a + 1)]);
  }
  int64_t numPair2 = c2(total) - numPair1 - numPair3;
  assert(numPair2 >= 0);
  std::cout << 1 * numPair1 + 2 * (c2(total) - numPair1 - numPair3) +
                   3 * numPair3
            << '\n';
}

```