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>
long long max(long long x, long long y) { return (x > y ? x : y); }
long long min(long long x, long long y) { return (x < y ? x : y); }
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
using namespace ::std;
const int maxn = 1e7 + 300;
const int inf = 1e9 + 800;
const int mod = 1e9 + 7;
int minn[maxn];
long long joft[maxn];
int n;
long long find_gcd_mos_1() {
  for (int i = n; i >= 1; i--) {
    long long res = n / i;
    for (int j = i; j <= n; j += i) {
      joft[i] -= joft[j];
    }
    joft[i] += (res * (res - 1)) / 2;
  }
  return joft[1];
}
int par[maxn];
long long find_dow_12() {
  fill(par, par + n + 7, 0);
  for (int i = 2; i <= n; i++) {
    if (minn[i] != i) par[minn[i]]++;
  }
  for (int i = 1; i <= n; i++) {
    par[i] += par[i - 1];
  }
  long long ans = 0;
  for (int i = 2; i <= n / 2; i++) {
    if (minn[i] == i) {
      ans += par[n / i];
      for (int j = i * 2; j <= n; j += i) {
        if ((long long)minn[j] * (long long)i <= n) {
          ans--;
        }
      }
    }
  }
  return ans;
}
long long find_dow_22() {
  fill(par, par + n + 7, 0);
  for (int i = 2; i <= n / 2; i++) {
    if (minn[i] == i) par[i]++;
  }
  for (int i = 1; i <= n; i++) {
    par[i] += par[i - 1];
  }
  long long ans = 0;
  for (int i = 2; i <= n / 2; i++) {
    if (minn[i] == i) {
      ans += par[n / i];
      if ((long long)i * (long long)i <= n) ans--;
    }
  }
  return ans / 2;
}
long long find_dow_11() {
  long long tedad = 0;
  for (int i = 2; i <= n; i++) {
    if (minn[i] != i) tedad++;
  }
  long long ans = 0;
  fill(joft, joft + n + 7, 0);
  for (int i = n; i >= 2; i--) {
    long long res = n / i;
    if (minn[i] == i) res--;
    for (int j = i; j <= n; j += i) {
      joft[i] -= joft[j];
    }
    joft[i] += (res * (res - 1)) / 2;
    ans += joft[i];
  }
  return tedad * (tedad - 1) / 2 - ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 2; i <= n; i++)
    if (minn[i] == 0)
      for (int j = i; j <= n; j += i)
        if (minn[j] == 0) minn[j] = i;
  long long bad = 1;
  for (int i = 2; i <= n; i++) {
    if (minn[i] == i && i > n / 2) {
      bad++;
    }
  }
  long long sefr = bad * (n - 1) - bad * (bad - 1) / 2;
  long long v = find_gcd_mos_1();
  long long yek = ((long long)n * ((long long)n - 1)) / 2 - v;
  long long a11 = find_dow_11();
  long long a12 = find_dow_12();
  long long a22 = find_dow_22();
  long long dow = a11 + a12 + a22;
  long long sew = ((long long)n * (long long)(n - 1)) / 2 - sefr - yek - dow;
  cout << yek + dow * 2 + sew * 3;
}