import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

public class Euler146 {
    static class ModFilter {
        int p;
        int step;
        boolean[] bad;
    }

    static boolean isPrime(long n) {
        if (n < 2) return false;
        long[] small = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
        for (long p : small) {
            if (n == p) return true;
            if (n % p == 0) return false;
        }
        return BigInteger.valueOf(n).isProbablePrime(20);
    }

    static List<Integer> sievePrimes(int limit) {
        boolean[] isPrime = new boolean[limit + 1];
        for (int i = 2; i <= limit; i++) isPrime[i] = true;
        for (int p = 2; p * p <= limit; p++) {
            if (isPrime[p]) {
                for (int q = p * p; q <= limit; q += p) {
                    isPrime[q] = false;
                }
            }
        }
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= limit; i++) {
            if (isPrime[i]) primes.add(i);
        }
        return primes;
    }

    static List<ModFilter> buildFilters(int limit) {
        long[] kGood = {1, 3, 7, 9, 13, 27};
        List<Integer> primes = sievePrimes(limit);
        List<ModFilter> filters = new ArrayList<>();
        for (int p : primes) {
            if (p == 2 || p == 5) continue;
            ModFilter f = new ModFilter();
            f.p = p;
            f.step = 10 % p;
            f.bad = new boolean[p];
            for (int r = 0; r < p; r++) {
                int r2 = (int) ((1L * r * r) % p);
                boolean bad = false;
                for (long k : kGood) {
                    if ((r2 + (k % p)) % p == 0) {
                        bad = true;
                        break;
                    }
                }
                f.bad[r] = bad;
            }
            filters.add(f);
        }
        return filters;
    }

    static long runSequence(long start, long end, long residue, List<ModFilter> filters) {
        long[] kGood = {1, 3, 7, 9, 13, 27};
        long[] kBad = {5, 11, 15, 17, 19, 21, 23, 25};
        long sum = 0;
        
        long step = 70;
        long currentMod = start % step;
        long n;
        if (currentMod <= residue) {
            n = start + (residue - currentMod);
        } else {
            n = start + (step - (currentMod - residue));
        }

        if (n >= end) return 0;

        long square = n * n;
        
        int[] residues = new int[filters.size()];
        int[] step70 = new int[filters.size()];
        for (int i = 0; i < filters.size(); i++) {
            ModFilter f = filters.get(i);
            residues[i] = (int) (n % f.p);
            step70[i] = (f.step * 7) % f.p;
        }

        while (n < end) {
            if (square % 3 != 0 && square % 13 != 0) {
                boolean ok = true;
                if (n >= 1000) {
                    for (int i = 0; i < filters.size(); i++) {
                        if (filters.get(i).bad[residues[i]]) {
                            ok = false;
                            break;
                        }
                    }
                }
                if (ok) {
                    for (long k : kGood) {
                        if (!isPrime(square + k)) {
                            ok = false;
                            break;
                        }
                    }
                    if (ok) {
                        for (long k : kBad) {
                            if (isPrime(square + k)) {
                                ok = false;
                                break;
                            }
                        }
                    }
                    if (ok) {
                        sum += n;
                    }
                }
            }
            n += step;
            square += 140 * (n - step) + 4900;
            for (int i = 0; i < filters.size(); i++) {
                int p = filters.get(i).p;
                int next = residues[i] + step70[i];
                if (next >= p) next -= p;
                residues[i] = next;
            }
        }
        return sum;
    }

    static long solve(long limit, List<ModFilter> filters) {
        int threads = Runtime.getRuntime().availableProcessors();
        if (threads < 1) threads = 1;
        long start = 10;
        long count = (limit - start + 9) / 10;
        long block = (count + threads - 1) / threads;
        
        return IntStream.range(0, threads).parallel().mapToLong(t -> {
            long idxStart = t * block;
            long idxEnd = Math.min(count, idxStart + block);
            long nStart = start + idxStart * 10;
            long nEnd = start + idxEnd * 10;
            long localSum = 0;
            localSum += runSequence(nStart, nEnd, 10, filters);
            localSum += runSequence(nStart, nEnd, 60, filters);
            return localSum;
        }).sum();
    }

    public static void main(String[] args) {
        long limit = 150000000L;
        List<ModFilter> filters = buildFilters(2000);
        System.out.println(solve(limit, filters));
    }
}