#include <bits/stdc++.h>
using namespace std;
const long long maxn = 1e7 + 1, msiz = 2, mod = 1e9 + 7, inf = 1e18;
long long dp[maxn], lp[maxn], sl[maxn];
vector<pair<long long, long long> > vt;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long n;
  cin >> n;
  for (int i = n; i > n / 2; i--) dp[i] = 1;
  for (int i = n / 2; i; i--) {
    dp[i] = (n / i) * (n / i);
    for (int j = i * 2; j <= n; j += i) dp[i] -= dp[j];
  }
  long long sl1 = n * (n - 1) - dp[1] + 1, sl3 = 0;
  for (int i = 2; i * i <= n; i++)
    if (!lp[i])
      for (int j = i * 2; j <= n; j += i)
        if (!lp[j]) lp[j] = i;
  for (int i = 2; i <= n; i++)
    if (!lp[i]) lp[i] = i;
  for (int i = n / 2 + 1; i <= n; i++)
    if (lp[i] == i) sl3++;
  for (int i = 2; i <= n; i++) sl[lp[i]]++;
  for (int i = 2; i <= n; i++)
    if (sl[i]) vt.push_back(make_pair(i, sl[i]));
  long long sl2 = 0;
  for (int i = 0; i < (int)(vt.size()); i++)
    for (int j = 0; j < (int)(vt.size()); j++)
      if (vt[i].first * vt[j].first > n)
        break;
      else {
        if (i == j)
          sl2 += vt[i].second * (vt[j].second - 1);
        else
          sl2 += vt[i].second * vt[j].second;
      }
  sl3 = sl3 * (n - sl3 - 1) * 2 + sl3 * (sl3 - 1);
  cout << (sl1 + (sl2 - sl1) * 2 + (((n - 2) * (n - 1)) - sl3 - sl2) * 3) / 2;
  return 0;
}

### Prompt

In CPP, your task is to solve 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 long long maxn = 1e7 + 1, msiz = 2, mod = 1e9 + 7, inf = 1e18;
long long dp[maxn], lp[maxn], sl[maxn];
vector<pair<long long, long long> > vt;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long n;
  cin >> n;
  for (int i = n; i > n / 2; i--) dp[i] = 1;
  for (int i = n / 2; i; i--) {
    dp[i] = (n / i) * (n / i);
    for (int j = i * 2; j <= n; j += i) dp[i] -= dp[j];
  }
  long long sl1 = n * (n - 1) - dp[1] + 1, sl3 = 0;
  for (int i = 2; i * i <= n; i++)
    if (!lp[i])
      for (int j = i * 2; j <= n; j += i)
        if (!lp[j]) lp[j] = i;
  for (int i = 2; i <= n; i++)
    if (!lp[i]) lp[i] = i;
  for (int i = n / 2 + 1; i <= n; i++)
    if (lp[i] == i) sl3++;
  for (int i = 2; i <= n; i++) sl[lp[i]]++;
  for (int i = 2; i <= n; i++)
    if (sl[i]) vt.push_back(make_pair(i, sl[i]));
  long long sl2 = 0;
  for (int i = 0; i < (int)(vt.size()); i++)
    for (int j = 0; j < (int)(vt.size()); j++)
      if (vt[i].first * vt[j].first > n)
        break;
      else {
        if (i == j)
          sl2 += vt[i].second * (vt[j].second - 1);
        else
          sl2 += vt[i].second * vt[j].second;
      }
  sl3 = sl3 * (n - sl3 - 1) * 2 + sl3 * (sl3 - 1);
  cout << (sl1 + (sl2 - sl1) * 2 + (((n - 2) * (n - 1)) - sl3 - sl2) * 3) / 2;
  return 0;
}

```