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

public class Euler753 {
    static long isqrtI64(long n) {
        if (n == 0)
            return 0;
        long x = (long) Math.sqrt(n);
        while ((x + 1) * (x + 1) <= n)
            x++;
        while (x * x > n)
            x--;
        return x;
    }

    static long FFormula(int p, List<Long> twentySevenU2) {
        if (p == 3) {
            return 2;
        }
        if (p < 5 || p % 3 == 0) {
            return 0;
        }
        if (p % 3 == 2) {
            return (long) (p - 1) * (p - 2);
        }

        long target = 4L * p;
        long tSel = 0;

        for (long v : twentySevenU2) {
            if (v > target) {
                break;
            }
            long rem = target - v;
            long t = isqrtI64(rem);
            if (t * t == rem) {
                tSel = (t % 3 == 1) ? t : -t;
                break;
            }
        }

        return (long) (p - 1) * (p - 8 + tSel);
    }

    public static String solve() {
        int kLimit = 6000000;
        byte[] isPrime = new byte[kLimit];
        for (int i = 2; i < kLimit; i++) {
            isPrime[i] = 1;
        }

        for (int i = 2; (long) i * i < kLimit; ++i) {
            if (isPrime[i] != 1)
                continue;
            for (int j = i * i; j < kLimit; j += i) {
                isPrime[j] = 0;
            }
        }

        List<Long> twentySevenU2 = new ArrayList<>();
        for (long u = 1;; ++u) {
            long v = 27L * u * u;
            if (v > 4L * kLimit) {
                break;
            }
            twentySevenU2.add(v);
        }

        long total = 0;
        for (int p = 2; p < kLimit; ++p) {
            if (isPrime[p] != 1)
                continue;
            total += FFormula(p, twentySevenU2);
        }

        return Long.toString(total);
    }

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