#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e7 + 5;
int N;
int p[MAXN];
int phi[MAXN];
vector<int> nums, primes;
int cnt[MAXN];
int suff[MAXN];
void load() { scanf("%d", &N); }
void init() {
  for (int i = 2; i <= N; i++)
    if (!p[i])
      for (int j = i; j <= N; j += i)
        if (!p[j]) p[j] = i;
  for (int i = 1; i <= N; i++) phi[i] = i;
  for (int i = 1; i <= N; i++)
    for (int j = 2 * i; j <= N; j += i) phi[j] -= phi[i];
}
long long solve() {
  long long x = (long long)N * (N - 1) / 2;
  for (int i = 2; i <= N; i++) x -= phi[i];
  for (int i = 2; i <= N; i++)
    if (p[i] < i || i <= N / 2) nums.push_back(i);
  for (auto it : nums) cnt[p[it]]++;
  for (int i = N; i; i--) cnt[i] += cnt[i + 1];
  long long z = 0;
  for (auto it : nums)
    if (p[it] == it)
      z += cnt[N / it + 1] - (it > N / it ? cnt[it] - cnt[it + 1] : 0);
  for (auto it : nums)
    if (p[it] == it) suff[it]++;
  for (int i = N; i; i--) suff[i] += suff[i + 1];
  long long sum = 0;
  for (auto it : nums)
    if (p[it] == it) sum += suff[N / it + 1] - (it > N / it);
  z -= sum / 2;
  return (long long)nums.size() * ((int)nums.size() - 1) + z - x;
}
int main() {
  load();
  init();
  printf("%lld\n", solve());
  return 0;
}

### Prompt

Develop a solution in cpp 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>
using namespace std;
const int MAXN = 1e7 + 5;
int N;
int p[MAXN];
int phi[MAXN];
vector<int> nums, primes;
int cnt[MAXN];
int suff[MAXN];
void load() { scanf("%d", &N); }
void init() {
  for (int i = 2; i <= N; i++)
    if (!p[i])
      for (int j = i; j <= N; j += i)
        if (!p[j]) p[j] = i;
  for (int i = 1; i <= N; i++) phi[i] = i;
  for (int i = 1; i <= N; i++)
    for (int j = 2 * i; j <= N; j += i) phi[j] -= phi[i];
}
long long solve() {
  long long x = (long long)N * (N - 1) / 2;
  for (int i = 2; i <= N; i++) x -= phi[i];
  for (int i = 2; i <= N; i++)
    if (p[i] < i || i <= N / 2) nums.push_back(i);
  for (auto it : nums) cnt[p[it]]++;
  for (int i = N; i; i--) cnt[i] += cnt[i + 1];
  long long z = 0;
  for (auto it : nums)
    if (p[it] == it)
      z += cnt[N / it + 1] - (it > N / it ? cnt[it] - cnt[it + 1] : 0);
  for (auto it : nums)
    if (p[it] == it) suff[it]++;
  for (int i = N; i; i--) suff[i] += suff[i + 1];
  long long sum = 0;
  for (auto it : nums)
    if (p[it] == it) sum += suff[N / it + 1] - (it > N / it);
  z -= sum / 2;
  return (long long)nums.size() * ((int)nums.size() - 1) + z - x;
}
int main() {
  load();
  init();
  printf("%lld\n", solve());
  return 0;
}

```