#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
int in() {
  int x;
  cin >> x;
  return x;
}
long long lin() {
  long long x;
  cin >> x;
  return x;
}
string stin() {
  string s;
  cin >> s;
  return s;
}
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
vector<int> iota(int n) {
  vector<int> a(n);
  iota(begin(a), end(a), 0);
  return a;
}
void print() { putchar(' '); }
void print(bool a) { cout << a; }
void print(int a) { cout << a; }
void print(long long a) { cout << a; }
void print(char a) { cout << a; }
void print(string& a) { cout << a; }
void print(double a) { cout << a; }
template <class T>
void print(const vector<T>&);
template <class T, size_t size>
void print(const array<T, size>&);
template <class T, class L>
void print(const pair<T, L>& p);
template <class T, size_t size>
void print(const T (&)[size]);
template <class T>
void print(const vector<T>& a) {
  if (a.empty()) return;
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
  cout << endl;
}
template <class T>
void print(const deque<T>& a) {
  if (a.empty()) return;
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
}
template <class T, size_t size>
void print(const array<T, size>& a) {
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
}
template <class T, class L>
void print(const pair<T, L>& p) {
  cout << '(';
  print(p.first);
  cout << ",";
  print(p.second);
  cout << ')';
}
template <class T, size_t size>
void print(const T (&a)[size]) {
  print(a[0]);
  for (auto i = a; ++i != end(a);) {
    cout << " ";
    print(*i);
  }
}
template <class T>
void print(const T& a) {
  cout << a;
}
int out() {
  putchar('\n');
  return 0;
}
template <class T>
int out(const T& t) {
  print(t);
  putchar('\n');
  return 0;
}
template <class Head, class... Tail>
int out(const Head& head, const Tail&... tail) {
  print(head);
  putchar(' ');
  out(tail...);
  return 0;
}
long long gcd(long long a, long long b) {
  while (b) {
    long long c = b;
    b = a % b;
    a = c;
  }
  return a;
}
long long lcm(long long a, long long b) {
  if (!a || !b) return 0;
  return a * b / gcd(a, b);
}
template <class... T>
void err(const T&...) {}
signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);
  long long n = in();
  if (n == 1) {
    cout << 0 << '\n';
    return 0;
  }
  vector<int> a(n + 1);
  for (long long i = 1; i <= n; ++i) a[i] = i;
  vector<int> p(n + 1, 1);
  p[1] = 1;
  vector<vector<long long> > div(n + 1);
  vector<long long> primes;
  for (long long i = 2; i <= n; ++i) {
    if (p[i]) {
      primes.push_back(i);
      for (int j = i * 2; j <= n; j += i) p[j] = 0;
    }
  }
  vector<int> min_prime(n + 1);
  vector<int> cnt(n + 1);
  for (long long i = 2; i <= n; ++i) {
    if (p[i]) {
      for (int j = i; j <= n; j += i) {
        if (!min_prime[j]) {
          min_prime[j] = 1;
          cnt[i]++;
        }
        a[j] /= i;
        a[j] *= i - 1;
      }
    }
  }
  vector<long long> rui(n + 1);
  for (long long i = 2; i <= n; ++i) rui[i] = rui[i - 1] + cnt[i];
  long long ans = 0;
  ans += n * (n - 1) / 2;
  for (long long i = 2; i <= n; ++i) ans += a[i];
  for (long long i = 2; i <= n; ++i) {
    ans += (long long)cnt[i] * max<long long>(0, rui[i - 1] - rui[n / i]);
  }
  ans -= (n - 1) * 2;
  long long C = 0;
  for (long long i = (n + 2) / 2; i <= n; ++i) {
    if (p[i]) ans -= (n - 2) * 3, C++;
  }
  ans += (C * (C - 1)) / 2 * 3;
  cout << ans << '\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>
#pragma GCC optimize("O3")
using namespace std;
int in() {
  int x;
  cin >> x;
  return x;
}
long long lin() {
  long long x;
  cin >> x;
  return x;
}
string stin() {
  string s;
  cin >> s;
  return s;
}
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
vector<int> iota(int n) {
  vector<int> a(n);
  iota(begin(a), end(a), 0);
  return a;
}
void print() { putchar(' '); }
void print(bool a) { cout << a; }
void print(int a) { cout << a; }
void print(long long a) { cout << a; }
void print(char a) { cout << a; }
void print(string& a) { cout << a; }
void print(double a) { cout << a; }
template <class T>
void print(const vector<T>&);
template <class T, size_t size>
void print(const array<T, size>&);
template <class T, class L>
void print(const pair<T, L>& p);
template <class T, size_t size>
void print(const T (&)[size]);
template <class T>
void print(const vector<T>& a) {
  if (a.empty()) return;
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
  cout << endl;
}
template <class T>
void print(const deque<T>& a) {
  if (a.empty()) return;
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
}
template <class T, size_t size>
void print(const array<T, size>& a) {
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
}
template <class T, class L>
void print(const pair<T, L>& p) {
  cout << '(';
  print(p.first);
  cout << ",";
  print(p.second);
  cout << ')';
}
template <class T, size_t size>
void print(const T (&a)[size]) {
  print(a[0]);
  for (auto i = a; ++i != end(a);) {
    cout << " ";
    print(*i);
  }
}
template <class T>
void print(const T& a) {
  cout << a;
}
int out() {
  putchar('\n');
  return 0;
}
template <class T>
int out(const T& t) {
  print(t);
  putchar('\n');
  return 0;
}
template <class Head, class... Tail>
int out(const Head& head, const Tail&... tail) {
  print(head);
  putchar(' ');
  out(tail...);
  return 0;
}
long long gcd(long long a, long long b) {
  while (b) {
    long long c = b;
    b = a % b;
    a = c;
  }
  return a;
}
long long lcm(long long a, long long b) {
  if (!a || !b) return 0;
  return a * b / gcd(a, b);
}
template <class... T>
void err(const T&...) {}
signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);
  long long n = in();
  if (n == 1) {
    cout << 0 << '\n';
    return 0;
  }
  vector<int> a(n + 1);
  for (long long i = 1; i <= n; ++i) a[i] = i;
  vector<int> p(n + 1, 1);
  p[1] = 1;
  vector<vector<long long> > div(n + 1);
  vector<long long> primes;
  for (long long i = 2; i <= n; ++i) {
    if (p[i]) {
      primes.push_back(i);
      for (int j = i * 2; j <= n; j += i) p[j] = 0;
    }
  }
  vector<int> min_prime(n + 1);
  vector<int> cnt(n + 1);
  for (long long i = 2; i <= n; ++i) {
    if (p[i]) {
      for (int j = i; j <= n; j += i) {
        if (!min_prime[j]) {
          min_prime[j] = 1;
          cnt[i]++;
        }
        a[j] /= i;
        a[j] *= i - 1;
      }
    }
  }
  vector<long long> rui(n + 1);
  for (long long i = 2; i <= n; ++i) rui[i] = rui[i - 1] + cnt[i];
  long long ans = 0;
  ans += n * (n - 1) / 2;
  for (long long i = 2; i <= n; ++i) ans += a[i];
  for (long long i = 2; i <= n; ++i) {
    ans += (long long)cnt[i] * max<long long>(0, rui[i - 1] - rui[n / i]);
  }
  ans -= (n - 1) * 2;
  long long C = 0;
  for (long long i = (n + 2) / 2; i <= n; ++i) {
    if (p[i]) ans -= (n - 2) * 3, C++;
  }
  ans += (C * (C - 1)) / 2 * 3;
  cout << ans << '\n';
}

```