import java.util.*;

public class Euler87 {
    static boolean[] sieve(int n) {
        boolean[] s = new boolean[n + 1];
        Arrays.fill(s, true);
        s[0] = s[1] = false;
        for (int p = 2; p * p <= n; p++)
            if (s[p])
                for (int q = p * p; q <= n; q += p)
                    s[q] = false;
        return s;
    }

    public static void main(String[] args) {
        int limit = 50000000;
        boolean[] s = sieve((int) Math.sqrt(limit) + 1);
        List<Long> sq = new ArrayList<>(), cb = new ArrayList<>(), ft = new ArrayList<>();
        for (int p = 2; p < s.length; p++)
            if (s[p]) {
                long p2 = (long) p * p;
                if (p2 < limit)
                    sq.add(p2);
                long p3 = p2 * p;
                if (p3 < limit)
                    cb.add(p3);
                long p4 = p3 * p;
                if (p4 < limit)
                    ft.add(p4);
            }
        Set<Integer> vals = new HashSet<>();
        for (long a : sq)
            for (long b : cb) {
                if (a + b >= limit)
                    break;
                for (long c : ft) {
                    long v = a + b + c;
                    if (v >= limit)
                        break;
                    vals.add((int) v);
                }
            }
        System.out.println(vals.size());
    }
}