#include <bits/stdc++.h>
using namespace std;
template <typename T1, typename T2>
string print_iterable(T1 begin_iter, T2 end_iter, int counter) {
  bool done_something = false;
  stringstream res;
  res << "[";
  for (; begin_iter != end_iter and counter; ++begin_iter) {
    done_something = true;
    counter--;
    res << *begin_iter << ", ";
  }
  string str = res.str();
  if (done_something) {
    str.pop_back();
    str.pop_back();
  }
  str += "]";
  return str;
}
vector<int> SortIndex(int size, std::function<bool(int, int)> compare) {
  vector<int> ord(size);
  for (int i = 0; i < size; i++) ord[i] = i;
  sort(ord.begin(), ord.end(), compare);
  return ord;
}
template <typename T>
bool MinPlace(T& a, const T& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool MaxPlace(T& a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename S, typename T>
ostream& operator<<(ostream& out, const pair<S, T>& p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}
template <typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
  out << "[";
  for (int i = 0; i < (int)v.size(); i++) {
    out << v[i];
    if (i != (int)v.size() - 1) out << ", ";
  }
  out << "]";
  return out;
}
const int MAXN = 1e7 + 10;
long long N;
int cntppp[MAXN];
int ppp[MAXN];
int phi[MAXN];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N;
  if (N <= 3) {
    cout << 0 << "\n";
    return 0;
  }
  for (int p = 2; p <= N; p++) {
    if (ppp[p]) continue;
    for (int i = p; i <= N; i += p) {
      if (ppp[i] == 0) {
        cntppp[p]++;
        ppp[i] = p;
      }
    }
  }
  phi[1] = 1;
  for (int k = 2; k <= N; k++) {
    int p = ppp[k];
    phi[k] = p - 1;
    int it = k / p;
    while (it % p == 0) it /= p, phi[k] *= p;
    phi[k] *= phi[it];
  }
  long long big_primes = 0;
  for (int i = 2; i <= N; i++) {
    if (ppp[i] == i and i * 2 > N) big_primes++;
  }
  long long appb = 0;
  for (long long i = 2; i <= N; i++) {
    if (ppp[i] != i) continue;
    for (long long j = i; i * j <= N; j++) {
      if (ppp[j] != j) continue;
      if (i != j)
        appb += (long long)cntppp[i] * (long long)cntppp[j];
      else
        appb += ((long long)cntppp[i] * ((long long)cntppp[i] - 1ll)) / 2ll;
    }
  }
  long long asimb = 0;
  for (long long i = 2; i <= N; i++) {
    asimb += i - 1 - phi[i];
  }
  long long all_pairs = ((N - big_primes - 1) * (N - big_primes - 2ll)) / 2ll;
  cout << 3ll * all_pairs - appb - asimb << "\n";
}

### Prompt

Please formulate 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;
template <typename T1, typename T2>
string print_iterable(T1 begin_iter, T2 end_iter, int counter) {
  bool done_something = false;
  stringstream res;
  res << "[";
  for (; begin_iter != end_iter and counter; ++begin_iter) {
    done_something = true;
    counter--;
    res << *begin_iter << ", ";
  }
  string str = res.str();
  if (done_something) {
    str.pop_back();
    str.pop_back();
  }
  str += "]";
  return str;
}
vector<int> SortIndex(int size, std::function<bool(int, int)> compare) {
  vector<int> ord(size);
  for (int i = 0; i < size; i++) ord[i] = i;
  sort(ord.begin(), ord.end(), compare);
  return ord;
}
template <typename T>
bool MinPlace(T& a, const T& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool MaxPlace(T& a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename S, typename T>
ostream& operator<<(ostream& out, const pair<S, T>& p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}
template <typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
  out << "[";
  for (int i = 0; i < (int)v.size(); i++) {
    out << v[i];
    if (i != (int)v.size() - 1) out << ", ";
  }
  out << "]";
  return out;
}
const int MAXN = 1e7 + 10;
long long N;
int cntppp[MAXN];
int ppp[MAXN];
int phi[MAXN];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N;
  if (N <= 3) {
    cout << 0 << "\n";
    return 0;
  }
  for (int p = 2; p <= N; p++) {
    if (ppp[p]) continue;
    for (int i = p; i <= N; i += p) {
      if (ppp[i] == 0) {
        cntppp[p]++;
        ppp[i] = p;
      }
    }
  }
  phi[1] = 1;
  for (int k = 2; k <= N; k++) {
    int p = ppp[k];
    phi[k] = p - 1;
    int it = k / p;
    while (it % p == 0) it /= p, phi[k] *= p;
    phi[k] *= phi[it];
  }
  long long big_primes = 0;
  for (int i = 2; i <= N; i++) {
    if (ppp[i] == i and i * 2 > N) big_primes++;
  }
  long long appb = 0;
  for (long long i = 2; i <= N; i++) {
    if (ppp[i] != i) continue;
    for (long long j = i; i * j <= N; j++) {
      if (ppp[j] != j) continue;
      if (i != j)
        appb += (long long)cntppp[i] * (long long)cntppp[j];
      else
        appb += ((long long)cntppp[i] * ((long long)cntppp[i] - 1ll)) / 2ll;
    }
  }
  long long asimb = 0;
  for (long long i = 2; i <= N; i++) {
    asimb += i - 1 - phi[i];
  }
  long long all_pairs = ((N - big_primes - 1) * (N - big_primes - 2ll)) / 2ll;
  cout << 3ll * all_pairs - appb - asimb << "\n";
}

```