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.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
const int maxn = 10010000;
using std::cin;
using std::cout;
inline long long c(int n) { return (long long)n * (n - 1) >> 1; }
int n, m;
int phi[maxn], d[maxn];
int cnt[maxn], pre[maxn];
int main() {
  std::ios::sync_with_stdio(false), cin.tie(0);
  cin >> n, m = n / 2 + 1;
  for (int i = 1; i <= n; ++i) phi[i] = i;
  for (int i = 2; i <= n; ++i)
    if (phi[i] == i)
      for (int j = i; j <= n; j += i) phi[j] = phi[j] / i * (i - 1);
  for (int i = n; i >= 2; --i)
    if (phi[i] == i - 1)
      for (int j = i; j <= n; j += i) d[j] = i;
  for (int i = 1; i <= n; ++i) ++cnt[d[i]];
  for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + cnt[i];
  long long c0 = 0, c1 = 0, c2 = 0, c3 = 0;
  c0 = n;
  for (int i = m; i <= n; ++i) c0 -= phi[i] == i - 1;
  c0 = c(n) - c(c0 - 1);
  for (int i = 2; i <= n; ++i) c1 += i - phi[i] - 1;
  for (int i = 1; i <= n; ++i) c2 += (long long)cnt[i] * pre[n / i];
  for (int i = 1; i <= n; ++i) c2 -= (long long)d[i] * d[i] <= n;
  c2 /= 2;
  c2 -= c1;
  c3 = c(n) - c0 - c1 - c2;
  cout << std::max<long long>(0, c1 + c2 * 2 + c3 * 3 - 1) << '\n';
}