public class Euler291 {

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

    static long qValue(long n) {
        return 2 * n * n + 2 * n + 1;
    }

    static long maxIndexForLimit(long limit) {
        if (limit <= 5)
            return 0;
        long m = (isqrt(2 * limit - 1) - 1) / 2;
        while (m > 0 && qValue(m) >= limit)
            m--;
        while (qValue(m + 1) < limit)
            m++;
        return m;
    }

    static long solveLimit(long limit) {
        int m = (int) maxIndexForLimit(limit);
        if (m == 0)
            return 0;

        long[] values = new long[m + 1];
        for (int i = 1; i <= m; i++) {
            values[i] = qValue(i);
        }

        byte[] composite = new byte[m + 1];
        long count = 0;

        for (int i = 1; i <= m; i++) {
            if (composite[i] == 0) {
                count++;
            }
            long prime = values[i];
            if (prime == 1)
                continue;

            for (long j = i + prime; j <= m; j += prime) {
                int ji = (int) j;
                composite[ji] = 1;
                long v = values[ji];
                while (v % prime == 0)
                    v /= prime;
                values[ji] = v;
            }

            long mod = (i + 1) % prime;
            long start = (mod == 0) ? prime : (prime - mod);
            if (start == i) {
                start += prime;
            }

            for (long j = start; j <= m; j += prime) {
                int ji = (int) j;
                composite[ji] = 1;
                long v = values[ji];
                while (v % prime == 0)
                    v /= prime;
                values[ji] = v;
            }
        }

        return count;
    }

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