import java.util.*;

public class Euler362 {

    static long isqrt(long n) {
        if (n < 0)
            return 0;
        long r = (long) Math.sqrt(n);
        while ((r + 1) <= n / (r + 1))
            r++;
        while (r > n / r)
            r--;
        return r;
    }

    static long icbrt(long n) {
        if (n < 0)
            return 0;
        long r = (long) Math.cbrt(n);
        while ((r + 1) * (r + 1) * (r + 1) <= n)
            r++;
        while (r * r * r > n)
            r--;
        return r;
    }

    static long iroot4(long n) {
        if (n < 0)
            return 0;
        long r = (long) Math.sqrt(Math.sqrt(n));
        while ((r + 1) * (r + 1) * (r + 1) * (r + 1) <= n)
            r++;
        while (r * r * r * r > n)
            r--;
        return r;
    }

    static long powCapped(long base, int exp, long cap) {
        long res = 1;
        for (int i = 0; i < exp; i++) {
            if (base != 0 && res > cap / base)
                return cap + 1;
            res *= base;
        }
        return res;
    }

    static long kthRootFloor(long n, int k) {
        if (k <= 1 || n <= 1)
            return n;
        long r = (long) Math.pow(n, 1.0 / k);
        if (r == 0)
            r = 1;
        while (powCapped(r + 1, k, n) <= n)
            r++;
        while (powCapped(r, k, n) > n)
            r--;
        return r;
    }

    static class PrimeTable {
        int limit;
        int[] primes;
        int[] piSmall;

        PrimeTable(int limit) {
            this.limit = limit;
            int[] lp = new int[limit + 1];
            List<Integer> prs = new ArrayList<>();

            for (int i = 2; i <= limit; i++) {
                if (lp[i] == 0) {
                    lp[i] = i;
                    prs.add(i);
                }
                for (int p : prs) {
                    long v = (long) p * i;
                    if (p > lp[i] || v > limit)
                        break;
                    lp[(int) v] = p;
                }
            }

            primes = new int[prs.size()];
            for (int i = 0; i < prs.size(); i++)
                primes[i] = prs.get(i);

            piSmall = new int[limit + 1];
            int ptr = 0;
            for (int i = 1; i <= limit; i++) {
                piSmall[i] = piSmall[i - 1];
                if (ptr < primes.length && primes[ptr] == i) {
                    piSmall[i]++;
                    ptr++;
                }
            }
        }
    }

    static class PrimeCounter {
        PrimeTable table;
        Map<Long, Long> piCache = new HashMap<>();
        Map<Long, Long> phiCache = new HashMap<>();

        static final int K_SMALL_PHI_PRIMES = 7;
        static final int K_SMALL_PHI_MOD = 510510;
        static final int K_PHI_CACHE_S_MAX = 128;
        static final long K_PHI_CACHE_X_MAX = 50000000000L;

        int[][] phiTable;

        PrimeCounter(PrimeTable table) {
            this.table = table;
            phiTable = new int[K_SMALL_PHI_MOD + 1][K_SMALL_PHI_PRIMES + 1];
            for (int n = 0; n <= K_SMALL_PHI_MOD; n++)
                phiTable[n][0] = n;
            for (int s = 1; s <= K_SMALL_PHI_PRIMES; s++) {
                int p = table.primes[s - 1];
                for (int n = 0; n <= K_SMALL_PHI_MOD; n++) {
                    phiTable[n][s] = phiTable[n][s - 1] - phiTable[n / p][s - 1];
                }
            }
        }

        long phi(long x, int s) {
            if (s == 0)
                return x;
            if (s <= K_SMALL_PHI_PRIMES) {
                long block = x / K_SMALL_PHI_MOD;
                long rem = x % K_SMALL_PHI_MOD;
                return block * phiTable[K_SMALL_PHI_MOD][s] + phiTable[(int) rem][s];
            }

            if (x <= table.limit && (long) table.primes[s - 1] * table.primes[s - 1] > x) {
                return table.piSmall[(int) x] - s + 1;
            }

            long ps = table.primes[s - 1];
            if (ps * ps > x)
                return pi(x) - s + 1;

            if (s <= K_PHI_CACHE_S_MAX && x <= K_PHI_CACHE_X_MAX) {
                long key = (x << 8) ^ s;
                if (phiCache.containsKey(key))
                    return phiCache.get(key);
                long ans = phi(x, s - 1) - phi(x / ps, s - 1);
                phiCache.put(key, ans);
                return ans;
            }

            return phi(x, s - 1) - phi(x / ps, s - 1);
        }

        long pi(long x) {
            if (x <= table.limit)
                return table.piSmall[(int) x];
            if (piCache.containsKey(x))
                return piCache.get(x);

            long a = pi(iroot4(x));
            long b = pi(isqrt(x));
            long c = pi(icbrt(x));

            long ans = phi(x, (int) a) + (b + a - 2) * (b - a + 1) / 2;
            for (long i = a + 1; i <= b; i++) {
                long w = x / table.primes[(int) (i - 1)];
                ans -= pi(w);
                if (i <= c) {
                    long bi = pi(isqrt(w));
                    for (long j = i; j <= bi; j++) {
                        long q = w / table.primes[(int) (j - 1)];
                        ans -= pi(q) - (j - 1);
                    }
                }
            }
            piCache.put(x, ans);
            return ans;
        }
    }

    static long fsfFromSignature(List<Integer> signature) {
        int r = signature.size();
        if (r == 0)
            return 0;

        List<Integer> masks = new ArrayList<>();
        for (int m = 1; m < (1 << r); m++)
            masks.add(m);
        masks.sort((a, b) -> {
            int pa = Integer.bitCount(a);
            int pb = Integer.bitCount(b);
            if (pa != pb)
                return Integer.compare(pb, pa);
            return Integer.compare(a, b);
        });

        int[][] maskBits = new int[masks.size()][];
        for (int i = 0; i < masks.size(); i++) {
            int mask = masks.get(i);
            int[] bits = new int[Integer.bitCount(mask)];
            int idx = 0;
            for (int k = 0; k < r; k++) {
                if (((mask >> k) & 1) == 1)
                    bits[idx++] = k;
            }
            maskBits[i] = bits;
        }

        byte[] remaining = new byte[r];
        for (int i = 0; i < r; i++)
            remaining[i] = signature.get(i).byteValue();
        Map<Long, Long> memo = new HashMap<>();

        return fsfDfs(0, maskBits, remaining, r, memo);
    }

    static long packRemaining(byte[] remaining, int r) {
        long packed = 0;
        for (int i = 0; i < r; i++)
            packed |= (long) remaining[i] << (6 * i);
        return packed;
    }

    static long fsfDfs(int pos, int[][] maskBits, byte[] remaining, int r, Map<Long, Long> memo) {
        if (pos == maskBits.length) {
            for (int i = 0; i < r; i++)
                if (remaining[i] != 0)
                    return 0;
            return 1;
        }

        long key = packRemaining(remaining, r) ^ ((long) pos * 0x9E3779B97F4A7C15L);
        if (memo.containsKey(key))
            return memo.get(key);

        int[] bits = maskBits[pos];
        int maxTake = Integer.MAX_VALUE;
        for (int bit : bits)
            maxTake = Math.min(maxTake, remaining[bit]);

        long total = 0;
        for (int take = 0;; take++) {
            total += fsfDfs(pos + 1, maskBits, remaining, r, memo);
            if (take == maxTake)
                break;
            for (int bit : bits)
                remaining[bit]--;
        }

        for (int bit : bits)
            remaining[bit] += maxTake;

        memo.put(key, total);
        return total;
    }

    static void generateSignaturesDfs(int[] primes, int pIdx, int lastExp, long current, long limit, List<Integer> cur,
            List<List<Integer>> out) {
        if (pIdx >= primes.length)
            return;
        long p = primes[pIdx];
        long pPow = 1;

        for (int e = 1; e <= lastExp; e++) {
            if (pPow > limit / p)
                break;
            pPow *= p;
            if (current > limit / pPow)
                break;

            long nextVal = current * pPow;
            cur.add(e);
            out.add(new ArrayList<>(cur));
            generateSignaturesDfs(primes, pIdx + 1, e, nextVal, limit, cur, out);
            cur.remove(cur.size() - 1);
        }
    }

    static List<List<Integer>> generateSignatures(long limit, PrimeTable table) {
        List<List<Integer>> signatures = new ArrayList<>();
        generateSignaturesDfs(table.primes, 0, 63, 1, limit, new ArrayList<>(), signatures);
        return signatures;
    }

    static void generateUniquePermutationsRec(Map<Integer, Integer> freq, int[] cur, int pos, List<List<Integer>> out) {
        if (pos == cur.length) {
            List<Integer> list = new ArrayList<>();
            for (int v : cur)
                list.add(v);
            out.add(list);
            return;
        }
        for (int val : new ArrayList<>(freq.keySet())) {
            int f = freq.get(val);
            if (f > 0) {
                freq.put(val, f - 1);
                cur[pos] = val;
                generateUniquePermutationsRec(freq, cur, pos + 1, out);
                freq.put(val, f);
            }
        }
    }

    static List<List<Integer>> generateUniquePermutations(List<Integer> signature) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int e : signature)
            freq.put(e, freq.getOrDefault(e, 0) + 1);
        List<List<Integer>> out = new ArrayList<>();
        generateUniquePermutationsRec(freq, new int[signature.size()], 0, out);
        return out;
    }

    static class OrderedPrimeTupleCounter {
        PrimeTable table;
        PrimeCounter primeCounter;

        OrderedPrimeTupleCounter(PrimeTable table, PrimeCounter primeCounter) {
            this.table = table;
            this.primeCounter = primeCounter;
        }

        long countForExponents(List<Integer> exponents, long limit) {
            int r = exponents.size();
            if (r == 0)
                return 0;
            if (r == 1) {
                long root = kthRootFloor(limit, exponents.get(0));
                return primeCounter.pi(root);
            }

            int[] tailSum = new int[r];
            int running = 0;
            for (int i = r - 1; i >= 0; i--) {
                running += exponents.get(i);
                tailSum[i] = running;
            }

            Map<Long, Long> memo = new HashMap<>();
            return countDfs(0, 0, limit, r, exponents, tailSum, memo);
        }

        long countDfs(int pos, int startIndex, long remLimit, int r, List<Integer> exponents, int[] tailSum,
                Map<Long, Long> memo) {
            if (pos == r)
                return 1;

            long key = remLimit ^ ((long) startIndex * 0x9E3779B97F4A7C15L) ^ ((long) pos * 0xC2B2AE3D27D4EB4FL);
            if (memo.containsKey(key))
                return memo.get(key);

            long result = 0;
            if (pos == r - 1) {
                int exp = exponents.get(pos);
                long root = kthRootFloor(remLimit, exp);
                long upto = primeCounter.pi(root);
                result = (upto > startIndex) ? (upto - startIndex) : 0;
                memo.put(key, result);
                return result;
            }

            int tail = tailSum[pos];
            long maxP = kthRootFloor(remLimit, tail);
            long upto = primeCounter.pi(maxP);
            if (upto > table.primes.length)
                upto = table.primes.length;

            int exp = exponents.get(pos);
            for (long idx = startIndex; idx < upto; idx++) {
                long p = table.primes[(int) idx];
                long pPow = powCapped(p, exp, remLimit);
                if (pPow > remLimit)
                    break;
                result += countDfs(pos + 1, (int) (idx + 1), remLimit / pPow, r, exponents, tailSum, memo);
            }

            memo.put(key, result);
            return result;
        }
    }

    static long solveFast(long limit) {
        long rootLimit = Math.max(isqrt(limit), 100);
        PrimeTable table = new PrimeTable((int) rootLimit);
        PrimeCounter primeCounter = new PrimeCounter(table);
        OrderedPrimeTupleCounter tupleCounter = new OrderedPrimeTupleCounter(table, primeCounter);

        List<List<Integer>> signatures = generateSignatures(limit, table);
        long total = 0;

        for (List<Integer> signature : signatures) {
            long fsf = fsfFromSignature(signature);
            List<List<Integer>> perms = generateUniquePermutations(signature);
            for (List<Integer> p : perms) {
                long cnt = tupleCounter.countForExponents(p, limit);
                total += fsf * cnt;
            }
        }

        return total;
    }

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

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