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

public class Euler861 {

    static class Solver {
        long N;
        int rN;
        ArrayList<Integer> primes = new ArrayList<>();
        long[] pc;
        HashMap<Integer, Long> cumulativeCache = new HashMap<>();
        long currentAns = 0;

        Solver(long n) {
            this.N = n;
            this.rN = (int) Math.sqrt(N);
            while ((long) (rN + 1) * (rN + 1) <= N)
                rN++;
            while ((long) rN * rN > N)
                rN--;

            primes.add(2);
            getPrimes(2 * rN);
            pc = lucy();
        }

        long q(int k) {
            if (k < 2)
                return 0;
            return cumulative(k) - cumulative(k - 1);
        }

        int powerOfTwoIndex(long x) {
            if (x == 1)
                return 0;
            if (x == 2)
                return 1;
            if (x == 4)
                return 2;
            if (x == 8)
                return 3;
            if (x == 16)
                return 4;
            return -1;
        }

        long cumulative(int k) {
            if (k < 2)
                return 0;
            if (cumulativeCache.containsKey(k)) {
                return cumulativeCache.get(k);
            }

            int twoK = 2 * k;
            currentAns = 0;
            ArrayList<Integer> cp = new ArrayList<>();

            dfs(0, N, 1, 1, cp, twoK, k);

            cumulativeCache.put(k, currentAns);
            return currentAns;
        }

        void getPrimes(int limit) {
            if (limit < 2)
                return;
            int[] sieve = new int[limit + 1];
            for (int i = 2; i <= limit; i += 2)
                sieve[i] = 2;

            for (int i = 3; i <= limit; i += 2) {
                if (sieve[i] == 0) {
                    primes.add(i);
                    sieve[i] = i;
                    if ((long) i * i <= limit) {
                        for (int j = i * i; j <= limit; j += 2 * i) {
                            if (sieve[j] == 0)
                                sieve[j] = i;
                        }
                    }
                }
            }
        }

        long pcAt(int idx) {
            if (idx >= 0) {
                return pc[idx];
            }
            return pc[pc.length - (-idx)];
        }

        long[] lucy() {
            int r = rN;
            long[] S = new long[2 * r + 1];

            for (int i = 0; i <= r; ++i) {
                S[i] = i - 1;
            }
            for (int i = r; i >= 1; --i) {
                S[S.length - i] = (N / i) - 1;
            }

            for (int p = 2; p <= r; ++p) {
                if (S[p] <= S[p - 1])
                    continue;

                long sp = S[p - 1];
                long p2 = (long) p * p;

                for (int i = 1; i <= r; ++i) {
                    if (N / i < p2)
                        break;
                    long ip = (long) i * p;
                    long nip = N / ip;
                    int idx = (nip <= (long) r) ? (int) nip : -(int) ip;

                    int atI = S.length - i;
                    int atIdx = (idx >= 0) ? idx : (S.length - (-idx));

                    S[atI] -= (S[atIdx] - sp);
                }

                for (int i = r; i >= 1; --i) {
                    if ((long) i < p2)
                        break;
                    S[i] -= (S[i / p] - sp);
                }
            }

            return S;
        }

        long rec(ArrayList<Integer> cp, int i, long n, long cn, int k2) {
            if (k2 == 1) {
                int idx = (cn < (long) rN) ? -(int) cn : (int) (N / cn);
                long ans = pcAt(idx) - i;
                if (ans < 0)
                    ans = 0;

                int startPrime = (i < primes.size()) ? primes.get(i) : Integer.MAX_VALUE;
                for (int p : cp) {
                    if ((long) p <= n && p >= startPrime) {
                        ans--;
                    }
                }
                return ans > 0 ? ans : 0;
            }

            long ans = 0;
            while (true) {
                if (i >= primes.size())
                    break;
                int p = primes.get(i);
                if (cp.contains(p)) {
                    i++;
                    continue;
                }
                long nn = n / p;
                if (nn < p)
                    break;

                ans += rec(cp, i + 1, nn, cn * p, k2 - 1);
                i++;
            }
            return ans;
        }

        void dfs(int i, long n, long c, long cb, ArrayList<Integer> cp, int twoK, int kMax) {
            for (int k0 = 2; k0 <= kMax; ++k0) {
                long twoK0 = 2 * k0;
                if (twoK0 % cb != 0)
                    continue;

                int k2 = powerOfTwoIndex(twoK0 / cb);
                if (k2 < 0)
                    continue;

                if (k2 == 0) {
                    currentAns++;
                } else {
                    currentAns += rec(cp, 0, N / c, c, k2);
                }
            }

            while (i < primes.size()) {
                long p = primes.get(i);
                long nn = n / (p * p);
                if (nn == 0)
                    break;

                long cc = c * p * p;
                int e = 2;
                cp.add((int) p);

                while (true) {
                    long mult = e + (e & 1);
                    if (cb <= twoK / mult) {
                        dfs(i + 1, nn, cc, cb * mult, cp, twoK, kMax);
                    }

                    if (nn < p)
                        break;
                    nn /= p;
                    cc *= p;
                    e++;
                }

                cp.remove(cp.size() - 1);
                i++;
            }
        }
    }

    public static String solve() {
        Solver s = new Solver(1000000000000L);
        long ans = 0;
        for (int k = 2; k <= 10; ++k) {
            ans += s.q(k);
        }
        return Long.toString(ans);
    }

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