import java.util.*;
import java.util.concurrent.*;

public class Euler935 {

    static int[] buildSpf(int n) {
        int[] spf = new int[n + 1];
        if (n >= 1)
            spf[1] = 1;
        int[] primes = new int[n / 10 + 10]; // Rough upper bound
        int primeCount = 0;

        for (int i = 2; i <= n; ++i) {
            if (spf[i] == 0) {
                spf[i] = i;
                if (primeCount < primes.length)
                    primes[primeCount++] = i;
            }
            for (int j = 0; j < primeCount; ++j) {
                int p = primes[j];
                long v = (long) i * p;
                if (v > n)
                    break;
                spf[(int) v] = p;
                if (p == spf[i])
                    break;
            }
        }
        return spf;
    }

    static int factorDistinct(int x, int[] spf, int[] out) {
        int cnt = 0;
        while (x > 1) {
            int p = spf[x];
            out[cnt++] = p;
            do {
                x /= p;
            } while (x > 1 && x % p == 0);
        }
        return cnt;
    }

    static long countRelprimesPie(int pmax, int k, int[] spf) {
        int[] fac = new int[10];
        int m = factorDistinct(k, spf, fac);
        int lim = 1 << m;
        long res = 0;

        for (int mask = 0; mask < lim; ++mask) {
            long prod = 1;
            int bits = 0;
            int mm = mask;
            boolean ok = true;

            while (mm != 0) {
                int b = Integer.numberOfTrailingZeros(mm);
                mm &= (mm - 1);
                bits++;
                int p = fac[b];

                if (prod > pmax / p) {
                    ok = false;
                    break;
                }
                prod *= p;
            }

            if (!ok)
                continue;
            long term = pmax / prod;
            if ((bits & 1) != 0) {
                res -= term;
            } else {
                res += term;
            }
        }
        return res;
    }

    public static String solve(int nMax) {
        int kMax = nMax + 4;
        int[] spf = buildSpf(kMax);
        int qMax = (kMax - 1) / 4;

        int threads = Runtime.getRuntime().availableProcessors();
        if (threads < 1)
            threads = 1;
        if (threads > 12)
            threads = 12;
        if (qMax < 200000)
            threads = 1;

        int chunk = (qMax + threads - 1) / threads;
        long[] partial = new long[threads];

        if (threads == 1) {
            long local = 0;
            for (int q = 1; q <= qMax; ++q) {
                int k = (q << 2) + 1;
                int n = k - 1;
                if (n <= nMax)
                    local += countRelprimesPie(q, k, spf);

                k = (q << 2) + 2;
                n = k - 2;
                if (n <= nMax)
                    local += countRelprimesPie(q, k, spf);

                k = (q << 2) + 3;
                n = k - 1;
                if (n <= nMax)
                    local += countRelprimesPie(q, k, spf);

                k = (q << 2) + 4;
                n = k - 4;
                if (n <= nMax)
                    local += countRelprimesPie(q, k, spf);
            }
            return Long.toString(local);
        }

        try {
            ExecutorService executor = Executors.newFixedThreadPool(threads);
            List<Callable<Void>> tasks = new ArrayList<>();

            for (int t = 0; t < threads; ++t) {
                final int threadIdx = t;
                final int lo = t * chunk + 1;
                final int hi = Math.min(qMax, (t + 1) * chunk);
                if (lo > hi)
                    continue;

                tasks.add(() -> {
                    long local = 0;
                    for (int q = lo; q <= hi; ++q) {
                        int k = (q << 2) + 1;
                        int n = k - 1;
                        if (n <= nMax)
                            local += countRelprimesPie(q, k, spf);

                        k = (q << 2) + 2;
                        n = k - 2;
                        if (n <= nMax)
                            local += countRelprimesPie(q, k, spf);

                        k = (q << 2) + 3;
                        n = k - 1;
                        if (n <= nMax)
                            local += countRelprimesPie(q, k, spf);

                        k = (q << 2) + 4;
                        n = k - 4;
                        if (n <= nMax)
                            local += countRelprimesPie(q, k, spf);
                    }
                    partial[threadIdx] = local;
                    return null;
                });
            }

            List<Future<Void>> results = executor.invokeAll(tasks);
            for (Future<Void> res : results) {
                res.get(); // wait for completion
            }
            executor.shutdown();

        } catch (Exception e) {
            e.printStackTrace();
        }

        long ans = 0;
        for (long val : partial) {
            ans += val;
        }
        return Long.toString(ans);
    }

    public static void main(String[] args) {
        System.out.println(solve(100000000));
    }
}