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 bool print = false;
const int MAXN = 14111000;
int prme[MAXN];
int zl[MAXN];
void sito(int n) {
  for (int i = 2; i <= n; i++) {
    if (prme[i] != 0) continue;
    prme[i] = i;
    for (int j = 2 * i; j <= n; j += i)
      if (prme[j] == 0) prme[j] = i;
  }
}
int sumanp[MAXN];
int sumapr[MAXN];
int main() {
  int n;
  scanf("%d", &n);
  if (n <= 3) {
    puts("0");
    return 0;
  }
  sito(n + 2);
  long long pary = (((long long)n) * ((long long)n - 1LL)) / 2LL;
  long long zera = 1;
  for (int i = ((n / 2) + 1); i <= (n); i++) {
    if (prme[i] == i) zera++;
  }
  if (print) printf("ZERA %lld\n", zera);
  long long parzer =
      (zera * ((long long)n - 1LL)) - (zera * (zera - 1LL)) / 2LL;
  long long parjed = 0;
  for (int i = (2); i <= (n); i++) {
    int i1 = i, zl = 0;
    int pop = 1;
    while (i1 > 1) {
      zl++;
      if (prme[i1] == pop) {
        pop = -1;
        break;
      }
      pop = prme[i1];
      i1 /= prme[i1];
    }
    if (pop == -1) continue;
    int zn = (zl % 2 == 1) ? 1 : -1;
    long long wyrazy = n / i;
    long long parlok = (wyrazy * (wyrazy - 1LL)) / 2LL;
    if (print) printf("%d %d:: %lld %lld\n", i, zn, wyrazy, parlok);
    parjed += parlok * zn;
  }
  long long partrzy = 0;
  long long par3pr = 0;
  for (int i = (2); i <= (n); i++) {
    if (prme[i] == i) {
      if (i > n / 2) continue;
      sumapr[prme[i]]++;
    } else
      sumanp[prme[i]]++;
  }
  for (int i = (2); i <= (n); i++)
    sumanp[i] += sumanp[i - 1], sumapr[i] += sumapr[i - 1];
  for (int i = (2); i <= (n); i++) {
    if (prme[i] == i && i <= n / 2) {
      if (print) printf("PRME %d\n", i);
      partrzy += sumanp[n] - sumanp[n / i];
      par3pr += sumapr[n] - sumapr[max(i, n / i)];
      if (print)
        printf("%lld:: %lld %lld, %lld %lld\n", (long long)n / i,
               (long long)sumanp[n], (long long)sumanp[n / i],
               (long long)sumapr[n], (long long)sumapr[max(i, n / i)]);
    }
  }
  partrzy += par3pr;
  long long pardwa = pary - parzer - parjed - partrzy;
  if (print)
    printf("0 %lld\n1 %lld\n2 %lld\n3 %lld\n", parzer, parjed, pardwa, partrzy);
  printf("%lld\n", parjed + 2LL * pardwa + 3LL * partrzy);
}