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>
using namespace std;
const int N = 1e7 + 11;
int n;
int phi[N], mp[N];
bool np[N];
int sum[N];
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;
  int cnt = 0;
  np[0] = np[1] = 1;
  for (int i = 2; i <= n; ++i) phi[i] = i;
  for (int i = 2; i <= n; ++i)
    if (!np[i]) {
      if (i > (n / 2)) cnt++;
      phi[i]--;
      mp[i] = i;
      for (int j = i + i; j <= n; j += i) {
        np[j] = 1;
        phi[j] -= phi[j] / i;
        if (!mp[j]) mp[j] = i;
      }
    }
  for (int i = 2; i <= n; ++i) sum[mp[i]]++;
  for (int i = 2; i <= n; ++i) sum[i] += sum[i - 1];
  long long tot = 1ll * (n - 1) * (n - 2) / 2 - 1ll * cnt * (n - 1 - cnt) -
                  1ll * cnt * (cnt - 1) / 2;
  long long ff = 0;
  for (int i = 2; i <= n; ++i) {
    ff += 1ll * (i - 1 - phi[i]);
  }
  long long gg = 0;
  for (int i = 2; i <= n; ++i) {
    gg += 1ll * (sum[i] - sum[i - 1]) * sum[n / i];
  }
  for (int i = 2; i <= n; ++i) {
    if (1ll * mp[i] * mp[i] <= n) gg--;
  }
  gg /= 2;
  long long res = ff + (gg - ff) * 2 + 3 * (tot - gg);
  cout << res << '\n';
}