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 long long INF = 4e18L + 1;
const int IINF = 2e9 + 1;
using namespace std;
template <class TH>
void _dbg(const char *sdbg, TH h) {
  cerr << sdbg << '=' << h << endl;
}
template <class TH, class... TA>
void _dbg(const char *sdbg, TH h, TA... a) {
  while (*sdbg != ',') cerr << *sdbg++;
  cerr << '=' << h << ',';
  _dbg(sdbg + 1, a...);
}
unsigned long long DOTESTU[6] = {61, 2, 3, 5, 7, 11};
unsigned long long mnozenie(unsigned long long x, unsigned long long y,
                            unsigned long long MOD) {
  unsigned long long maska = 15, wynik = 0;
  while (y > 0) {
    wynik = (wynik + (maska & y) * x) % MOD;
    x = (x << 4) % MOD;
    y >>= 4;
  }
  return wynik;
}
long long sito[10000001 + 1];
vector<pair<unsigned long long, int> > rozloz(long long M) {
  vector<long long> V = {M};
  vector<pair<unsigned long long, int> > Odp;
  while (V.size()) {
    long long pom = V.back(), dz;
    V.pop_back();
    if (pom == 1) continue;
    dz = sito[pom];
    if (dz == pom) {
      int ile = 1;
      for (auto &el : V) {
        while (el % dz == 0) {
          ile++;
          el /= dz;
        }
      }
      Odp.push_back({dz, ile});
    } else {
      V.push_back(max(dz, pom / dz));
      V.push_back(min(dz, pom / dz));
    }
  }
  return Odp;
}
void sito_eratostenesa() {
  for (int i = 2; i <= 10000001; i++) sito[i] = i;
  for (int i = 2; i * i <= 10000001; i++)
    if (sito[i] == i)
      for (int j = 2 * i; j <= 10000001; j += i)
        if (sito[j] == j) sito[j] = i;
}
int wej_n;
int tab[100];
long long ile1(long long n) {
  long long n2 = n;
  long long roz = 0;
  while (n2 > 1) {
    long long akt = sito[n2];
    tab[roz] = akt;
    roz++;
    while (n2 % akt == 0) n2 /= akt;
  }
  long long res = 0;
  for (int i = 1; i < (1 << roz); i++) {
    long long mnoz = -1;
    if (__builtin_popcount(i) & 1) mnoz = 1;
    long long co = 1;
    for (int j = 0; j < roz; j++)
      if (i & (1 << j)) co *= tab[j];
    res += (n / co) * mnoz;
  }
  return res;
}
const int pot = (1 << 24);
int drzewo[2 * pot];
void dodaj(int gdzie) {
  gdzie += pot;
  drzewo[gdzie]++;
  while (gdzie > 0) {
    gdzie >>= 1;
    drzewo[gdzie]++;
  }
}
int suma(int a, int b) {
  a += pot, b += pot;
  if (a == b) return drzewo[a];
  int wyn = drzewo[a] + drzewo[b];
  while ((a >> 1) != (b >> 1)) {
    if ((a & 1) == 0) wyn += drzewo[a + 1];
    if ((b & 1) == 1) wyn += drzewo[b - 1];
    a >>= 1;
    b >>= 1;
  }
  return wyn;
}
long long pierwsze_pref[10000007];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  wej_n = n;
  sito_eratostenesa();
  for (int i = 2; i <= 10000000; i++) {
    pierwsze_pref[i] = pierwsze_pref[i - 1];
    if (sito[i] == i) pierwsze_pref[i]++;
  }
  long long odp = 0;
  long long zli = 1;
  for (int i = 2; i <= n; i++) {
    long long temp;
    long long najmniejsza;
    long long pomm;
    long long w_trzech;
    long long wcale;
    long long w_dwoch;
    if (sito[i] != i) {
      temp = ile1(i) - 1;
      najmniejsza = sito[i];
      pomm = min(n / najmniejsza, (long long)i - 1);
      w_trzech = pierwsze_pref[min(n / 2, i - 1)] - pierwsze_pref[pomm];
      wcale = 1;
      if (i > n / 2) wcale += pierwsze_pref[i - 1] - pierwsze_pref[n / 2];
      w_dwoch = i - 1 - temp - w_trzech - wcale;
    }
    if (sito[i] == i) {
      temp = 0;
      w_dwoch = suma(0, n / i);
      (i, n / i);
      wcale = zli;
      if (i * 2 > n) wcale = i - 1;
      w_trzech = i - 1 - temp - w_dwoch - wcale;
    }
    dodaj(sito[i]);
    (i, sito[i]);
    if (sito[i] == i && i * 2 > n) zli++;
    odp += temp + 2ll * w_dwoch + 3ll * w_trzech;
    (i, temp, w_dwoch, w_trzech, wcale);
  }
  cout << odp;
  return 0;
}