import java.util.ArrayList;
import java.util.HashMap;

public class Euler787 {

    static class MertensPrefix {
        int limit;
        int[] prefMu;
        HashMap<Long, Long> memoMu;
        HashMap<Long, Long> memoOddMu;

        MertensPrefix(int lim) {
            limit = lim;
            prefMu = new int[lim + 1];

            int[] mu = new int[lim + 1];
            ArrayList<Integer> primes = new ArrayList<>();
            boolean[] composite = new boolean[lim + 1];

            mu[1] = 1;
            for (int i = 2; i <= lim; ++i) {
                if (!composite[i]) {
                    primes.add(i);
                    mu[i] = -1;
                }
                for (int p : primes) {
                    long v = (long) i * p;
                    if (v > lim)
                        break;
                    composite[(int) v] = true;
                    if (i % p == 0) {
                        mu[(int) v] = 0;
                        break;
                    }
                    mu[(int) v] = -mu[i];
                }
            }

            for (int i = 1; i <= lim; ++i) {
                prefMu[i] = prefMu[i - 1] + mu[i];
            }

            memoMu = new HashMap<>(); // Primitives mappings would be faster but this requires less external libraries
            memoOddMu = new HashMap<>();
        }

        long muPrefix(long n) {
            if (n <= limit) {
                return prefMu[(int) n];
            }
            Long cached = memoMu.get(n);
            if (cached != null) {
                return cached;
            }

            long ans = 1;
            long l = 2;
            while (l <= n) {
                long q = n / l;
                long r = n / q;
                ans -= (r - l + 1) * muPrefix(q);
                l = r + 1;
            }

            memoMu.put(n, ans);
            return ans;
        }

        long oddMuPrefix(long n) {
            if (n <= 0)
                return 0;
            Long cached = memoOddMu.get(n);
            if (cached != null)
                return cached;

            long ans = 0;
            long cur = n;
            while (cur > 0) {
                ans += muPrefix(cur);
                cur >>= 1;
            }

            memoOddMu.put(n, ans);
            return ans;
        }
    }

    static long sumTotients(long n, MertensPrefix mp) {
        long s = 0;
        long l = 1;
        while (l <= n) {
            long q = n / l;
            long r = n / q;
            long muSeg = mp.muPrefix(r) - mp.muPrefix(l - 1);
            s += muSeg * q * q;
            l = r + 1;
        }
        return (s + 1) / 2;
    }

    static long fOddFloorSum(long m) {
        long k = (m + 1) / 2;
        long p = k / 2;
        if ((k & 1) == 1) {
            return p * p;
        }
        return p * (p - 1);
    }

    static long solveFast(long n) {
        int sieveLimit = 2000000;
        MertensPrefix mp = new MertensPrefix(sieveLimit);

        long total = sumTotients(n, mp) - 1;

        long losingHalf = 0;
        long l = 1;
        while (l <= n) {
            long q = n / l;
            long r = n / q;
            long oddMuSeg = mp.oddMuPrefix(r) - mp.oddMuPrefix(l - 1);
            losingHalf += oddMuSeg * fOddFloorSum(q);
            l = r + 1;
        }

        long losing = 2 * losingHalf;
        return total - losing;
    }

    public static String solve() {
        return Long.toString(solveFast(1000000000L));
    }

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