import java.util.ArrayList;
import java.util.List;

public class Euler967 {

    static List<Integer> primesUpTo(int n) {
        boolean[] isPrime = new boolean[n + 1];
        for (int i = 2; i <= n; i++)
            isPrime[i] = true;

        for (int i = 2; i * i <= n; ++i) {
            if (!isPrime[i])
                continue;
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }

        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; ++i) {
            if (isPrime[i]) {
                primes.add(i);
            }
        }
        return primes;
    }

    static long[][] buildBinom(int n) {
        long[][] c = new long[n + 1][n + 1];
        for (int i = 0; i <= n; ++i) {
            c[i][0] = 1;
            c[i][i] = 1;
            for (int j = 1; j < i; ++j) {
                c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
            }
        }
        return c;
    }

    static long[][] buildWeights(int maxA, int maxB) {
        int dim = Math.max(maxA, maxB);
        long[][] binom = buildBinom(dim);

        long[][] w = new long[maxA + 1][maxB + 1];

        for (int a = 0; a <= maxA; ++a) {
            for (int b = 0; b <= maxB; ++b) {
                long value = 0;
                for (int i = 0; i <= a; ++i) {
                    for (int j = 0; j <= b; ++j) {
                        if ((i + 2 * j) % 3 != 0)
                            continue;

                        long term = binom[a][i] * binom[b][j];
                        if (((i + j) & 1) != 0) {
                            term = -term;
                        }
                        value += term;
                    }
                }
                if (((a + b) & 1) != 0) {
                    value = -value;
                }
                w[a][b] = value;
            }
        }
        return w;
    }

    static class DFSContext {
        long N;
        List<Integer> primes;
        long[][] w;
        long answer = 0;

        void dfs(int idx, long product, int countA, int countB) {
            if (idx == primes.size()) {
                long weight = w[countA][countB];
                if (weight >= 0) {
                    answer += weight * (N / product);
                } else {
                    answer -= (-weight) * (N / product);
                }
                return;
            }

            dfs(idx + 1, product, countA, countB);

            long p = primes.get(idx);
            if (product > N / p) {
                return;
            }

            if (p % 3 == 1) {
                dfs(idx + 1, product * p, countA + 1, countB);
            } else {
                dfs(idx + 1, product * p, countA, countB + 1);
            }
        }
    }

    static long solveImpl(long N, int B) {
        List<Integer> rawPrimes = primesUpTo(B);
        List<Integer> primes = new ArrayList<>();
        int maxA = 0;
        int maxB = 0;

        for (int p : rawPrimes) {
            if (p == 3)
                continue;
            primes.add(p);
            if (p % 3 == 1) {
                maxA++;
            } else {
                maxB++;
            }
        }

        DFSContext ctx = new DFSContext();
        ctx.N = N;
        ctx.primes = primes;
        ctx.w = buildWeights(maxA, maxB);
        ctx.dfs(0, 1, 0, 0);

        return ctx.answer;
    }

    public static String solve() {
        return Long.toString(solveImpl(1000000000000000000L, 120));
    }

    public static void main(String[] args) {
        if (solveImpl(10, 4) != 5) {
            System.out.println("Validation failed");
            return;
        }
        if (solveImpl(10, 10) != 3) {
            System.out.println("Validation failed");
            return;
        }
        if (solveImpl(100, 10) != 41) {
            System.out.println("Validation failed");
            return;
        }
        System.out.println(solve());
    }
}