#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int)1e7 + 42;
const int64_t mod = (int64_t)1e9 + 7;
template <class T>
struct fenwick {
  int sz;
  T tr[MAXN];
  void init(int n) {
    sz = n + 1;
    memset(tr, 0, sizeof(tr));
  }
  T query(int idx) {
    T ans = 0;
    for (; idx >= 1; idx -= (idx & -idx)) ans += tr[idx];
    return ans;
  }
  void update(int idx, T val) {
    if (idx <= 0) return;
    for (; idx <= sz; idx += (idx & -idx)) tr[idx] += val;
  }
  T query(int l, int r) { return query(r) - query(l - 1); }
};
int n;
void read() { cin >> n; }
int64_t answer = 0;
int64_t cnt[MAXN], c[MAXN];
int lp[MAXN];
int64_t C(int64_t x) { return x * 1ll * (x - 1) / 2ll; }
fenwick<int64_t> t;
void solve() {
  t.init(n);
  for (int i = 2; i <= n; i++)
    if (lp[i] == 0)
      for (int x = i; x <= n; x += i)
        if (lp[x] == 0) lp[x] = i;
  for (int i = 2; i <= n; i++)
    cnt[i] += (n - i) / i + 1, c[i] += (n - i) / i + 1;
  for (int i = 2; i <= n; i++) cnt[i] = C(cnt[i]);
  for (int i = n; i >= 1; i--)
    for (int x = i * 2; x <= n; x += i) cnt[i] -= cnt[x];
  for (int i = 2; i <= n; i++) answer -= cnt[i];
  for (int i = 2; i <= n; i++) t.update(lp[i], 1);
  for (int i = 2; i <= n; i++) {
    t.update(lp[i], -1);
    int64_t cnt2 = t.query(n / lp[i]);
    int64_t cnt3 = t.query(n / 2);
    cnt3 -= cnt2;
    answer += cnt2 * 2ll;
    if (lp[i] * 2 <= n) answer += cnt3 * 3ll;
  }
  cout << answer << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  read();
  solve();
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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 MAXN = (int)1e7 + 42;
const int64_t mod = (int64_t)1e9 + 7;
template <class T>
struct fenwick {
  int sz;
  T tr[MAXN];
  void init(int n) {
    sz = n + 1;
    memset(tr, 0, sizeof(tr));
  }
  T query(int idx) {
    T ans = 0;
    for (; idx >= 1; idx -= (idx & -idx)) ans += tr[idx];
    return ans;
  }
  void update(int idx, T val) {
    if (idx <= 0) return;
    for (; idx <= sz; idx += (idx & -idx)) tr[idx] += val;
  }
  T query(int l, int r) { return query(r) - query(l - 1); }
};
int n;
void read() { cin >> n; }
int64_t answer = 0;
int64_t cnt[MAXN], c[MAXN];
int lp[MAXN];
int64_t C(int64_t x) { return x * 1ll * (x - 1) / 2ll; }
fenwick<int64_t> t;
void solve() {
  t.init(n);
  for (int i = 2; i <= n; i++)
    if (lp[i] == 0)
      for (int x = i; x <= n; x += i)
        if (lp[x] == 0) lp[x] = i;
  for (int i = 2; i <= n; i++)
    cnt[i] += (n - i) / i + 1, c[i] += (n - i) / i + 1;
  for (int i = 2; i <= n; i++) cnt[i] = C(cnt[i]);
  for (int i = n; i >= 1; i--)
    for (int x = i * 2; x <= n; x += i) cnt[i] -= cnt[x];
  for (int i = 2; i <= n; i++) answer -= cnt[i];
  for (int i = 2; i <= n; i++) t.update(lp[i], 1);
  for (int i = 2; i <= n; i++) {
    t.update(lp[i], -1);
    int64_t cnt2 = t.query(n / lp[i]);
    int64_t cnt3 = t.query(n / 2);
    cnt3 -= cnt2;
    answer += cnt2 * 2ll;
    if (lp[i] * 2 <= n) answer += cnt3 * 3ll;
  }
  cout << answer << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  read();
  solve();
  return 0;
}

```