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

public class Euler313 {
    static List<Integer> sievePrimes(int limit) {
        byte[] isPrime = new byte[limit + 1];
        for (int i = 2; i <= limit; i++) {
            isPrime[i] = 1;
        }

        for (int p = 2; (long) p * p <= limit; ++p) {
            if (isPrime[p] == 0)
                continue;
            for (int q = p * p; q <= limit; q += p) {
                isPrime[q] = 0;
            }
        }

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

    static long countGridsForPrimeSquare(long p2) {
        if ((p2 & 1) == 0)
            return 0;
        long h = (p2 + 13) / 2;
        long low = h / 4 + 1;
        long high = (h >= 2) ? ((h - 2) / 3) : 0;
        if (high < low)
            return 0;
        return 2 * (high - low + 1);
    }

    public static String solve() {
        int primeLimit = 1000000;
        List<Integer> primes = sievePrimes(primeLimit - 1);
        long total = 0;
        for (int p : primes) {
            long p2 = (long) p * p;
            total += countGridsForPrimeSquare(p2);
        }
        return String.valueOf(total);
    }

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