import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Euler428 {
    static long isqrt(long n) {
        long r = (long) Math.sqrt((double) n);
        while ((r + 1) * (r + 1) <= n)
            r++;
        while (r * r > n)
            r--;
        return r;
    }

    static class NecklaceCounter {
        long maxN;
        int[] mu;

        Map<Long, Long> cacheC6 = new HashMap<>();
        Map<Long, Long> cacheA0 = new HashMap<>();
        Map<Long, Long> cacheChisq = new HashMap<>();
        Map<Long, Long> cacheFg = new HashMap<>();
        Map<Long, Long> cacheSh = new HashMap<>();
        Map<Long, Long> cacheSd2 = new HashMap<>();
        Map<Long, Long> cacheSd4 = new HashMap<>();
        Map<Long, Long> cacheSd12 = new HashMap<>();
        Map<Long, Long> cacheSd36 = new HashMap<>();

        NecklaceCounter(long maxN) {
            this.maxN = maxN;
            int limit = (int) isqrt(maxN) + 5;
            mu = new int[limit + 1];
            initMu(limit);
        }

        void initMu(int limit) {
            int[] isComp = new int[limit + 1];
            List<Integer> primes = new ArrayList<>();
            mu[1] = 1;

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

        long squarefreeCount(long n) {
            if (n <= 0)
                return 0;
            long r = isqrt(n);
            long s = 0;
            for (long k = 1; k <= r; k++) {
                s += (long) mu[(int) k] * (n / (k * k));
            }
            return s;
        }

        long Sc6(long n) {
            if (n <= 0)
                return 0;
            if (cacheC6.containsKey(n))
                return cacheC6.get(n);
            long res = squarefreeCount(n) - Sc6(n / 2) - Sc6(n / 3) - Sc6(n / 6);
            cacheC6.put(n, res);
            return res;
        }

        long A0(long n) {
            if (n <= 0)
                return 0;
            if (cacheA0.containsKey(n))
                return cacheA0.get(n);
            long res = 0;
            long l = 1;
            while (l <= n) {
                long v = n / l;
                long r = n / v;
                res += v * (Sc6(r) - Sc6(l - 1));
                l = r + 1;
            }
            cacheA0.put(n, res);
            return res;
        }

        long FD(long n, int D) {
            if (n <= 0)
                return 0;
            if (D == 1)
                return A0(n) + A0(n / 2) + A0(n / 3) + A0(n / 6);
            if (D == 2)
                return 2 * A0(n) + 2 * A0(n / 3);
            if (D == 4)
                return 3 * A0(n) + 3 * A0(n / 3) - A0(n / 2) - A0(n / 6);
            if (D == 12)
                return 6 * A0(n) - 2 * A0(n / 2);
            if (D == 36)
                return 9 * A0(n) - 3 * A0(n / 2) - 3 * A0(n / 3) + A0(n / 6);
            return 0;
        }

        long SD(long n, int D) {
            if (n <= 0)
                return 0;
            Map<Long, Long> cache;
            if (D == 2)
                cache = cacheSd2;
            else if (D == 4)
                cache = cacheSd4;
            else if (D == 12)
                cache = cacheSd12;
            else if (D == 36)
                cache = cacheSd36;
            else
                return 0;

            if (cache.containsKey(n))
                return cache.get(n);

            long res = 0;
            long l = 1;
            while (l <= n) {
                long v = n / l;
                long r = n / v;
                res += v * (FD(r, D) - FD(l - 1, D));
                l = r + 1;
            }
            cache.put(n, res);
            return res;
        }

        long sumChiPrefix(long n) {
            if (n <= 0)
                return 0;
            return (n % 3 == 1) ? 1 : 0;
        }

        long Schisq(long n) {
            if (n <= 0)
                return 0;
            if (cacheChisq.containsKey(n))
                return cacheChisq.get(n);
            long r = isqrt(n);
            long s = 0;
            for (long k = 1; k <= r; k++) {
                if (k % 3 == 0)
                    continue;
                s += (long) mu[(int) k] * sumChiPrefix(n / (k * k));
            }
            cacheChisq.put(n, s);
            return s;
        }

        long FG(long n) {
            if (n <= 0)
                return 0;
            if (cacheFg.containsKey(n))
                return cacheFg.get(n);
            long res = 0;
            long l = 1;
            while (l <= n) {
                long v = n / l;
                long r = n / v;
                res += v * (Schisq(r) - Schisq(l - 1));
                l = r + 1;
            }
            cacheFg.put(n, res);
            return res;
        }

        long F1(long n) {
            if (n <= 0)
                return 0;
            return FG(n) - FG(n / 3);
        }

        long Sh(long n) {
            if (n <= 0)
                return 0;
            if (cacheSh.containsKey(n))
                return cacheSh.get(n);
            long res = 0;
            long l = 1;
            while (l <= n) {
                long v = n / l;
                long r = n / v;
                if (v % 3 == 1) {
                    res += F1(r) - F1(l - 1);
                }
                l = r + 1;
            }
            cacheSh.put(n, res);
            return res;
        }

        long T(long n) {
            long s2 = SD(n, 2);
            long s12 = SD(n, 12);
            long s4 = SD(n, 4);
            long s36n3 = SD(n / 3, 36);

            long cNot3 = (s4 - s36n3 - Sh(n)) / 2;

            long cDiv3 = 0;
            long m = n / 3;
            long t = 1;
            while (m > 0) {
                long term = SD(m, 4) - SD(m / 3, 36);
                cDiv3 += (2 * t - 1) * term;
                t++;
                m /= 3;
            }

            return s2 + s12 + cNot3 + cDiv3;
        }
    }

    public static String solve() {
        long target = 1000000000L;
        NecklaceCounter solver = new NecklaceCounter(target);
        return Long.toString(solver.T(target));
    }

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