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 JAVA):

Solution:
import java.util.*;
import java.io.*;

public class D {
    FastScanner in;
    PrintWriter out;

    public static void main(String[] args) {
        new D().run();
    }

    void solve() throws IOException {
        int n = in.nextInt();
        long m = 1; // one is bad number
        int[] primes = new int[n + 1];
        int[] primesMin = new int[n + 1];
        int primesCnt = 0;
        int[] sieve = new int[n + 1];
        for (int i = 2; i < n + 1; i++) {
            if (sieve[i] == 0) {
                primes[primesCnt++] = i;
                if (2 * i > n) {
                    m++;
                }
                int cnt = 0;
                for (int j = i; j < n + 1; j += i) {
                    if (sieve[j] == 0) {
                        sieve[j] = i;
                        cnt++;
                    }
                }
                primesMin[primesCnt - 1] = cnt;
            }
        }
        int[] prefPrimesMin = new int[n + 1];
        for (int i = 0; i < primesCnt; i++) {
            prefPrimesMin[i + 1] = prefPrimesMin[i] + primesMin[i];
        }   
        boolean[] squareFree = new boolean[n + 1];
        squareFree[1] = true;
        for (int i = 2; i < n + 1; i++) {
            int prev = i / sieve[i];
            squareFree[i] = prev % sieve[i] != 0 && squareFree[prev];
//            out.print(squareFree[i] + " ");
        }
//        out.println();

        int[] countPrimeInDecomposition = new int[n + 1];
        for (int i = 2; i < n + 1; i++) {
            if (sieve[i] == 0) {
                countPrimeInDecomposition[i] = 1;
            } else {
                countPrimeInDecomposition[i] = 1 + countPrimeInDecomposition[i / sieve[i]];
            }
        }
        long sum1 = 0;
        for (int i = 2; i < n + 1; i++) {
            if (!squareFree[i]) continue;
            long cnt = n / i;
            cnt *= cnt;
            if (countPrimeInDecomposition[i] % 2 == 0) {
                sum1 -= cnt;
            } else {
                sum1 += cnt;
            }
        }
        long sum0 = 2 * (n - m) * m + m * (m - 1) + 1;
//        out.println(sum0);
        long sum3 = 0;
        int p1i = -1;
        for (int pi = 0; pi < primesCnt; pi++) {
            long p2 = primes[pi];
            if (p2 * 2 > n) {
                break;
            }
            if (p2 * p2 > n) {
                if (p1i == -1) {
                    p1i = pi;
                }
                while (p1i >= 0 && primes[p1i] * p2 > n) {
                    p1i--;
                }
                p1i++;
                sum3 += prefPrimesMin[pi] - prefPrimesMin[p1i];
            }
        }
        sum3 *= 2;
        long sum2 = (long) n * n - sum0 - sum1 - sum3;
//        out.println(m + " " + sum0 + " " + sum1 + " " + sum2 + " " + sum3);
        out.println((sum1 + sum2 * 2 + sum3 * 3 - (n - 1)) / 2);
    }

    void run() {
        try {
            in = new FastScanner(System.in);
            out = new PrintWriter(System.out);
            solve();

            out.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        FastScanner(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}