public class Euler580 {
    public static String solve() {
        long LIMIT = (long) 1e16;
        long inc = LIMIT - 1;
        int mu = (int) Math.sqrt((double) inc);
        int oddCnt = mu / 2 + 1;
        boolean[] composite = new boolean[oddCnt];
        java.util.List<Integer> oddPrimes = new java.util.ArrayList<>();
        for (int idx = 1; idx < oddCnt; idx++) {
            if (composite[idx])
                continue;
            int p = 2 * idx + 1;
            oddPrimes.add(p);
            if (p <= mu / p) {
                int mark = (p * p - 1) / 2;
                while (mark < oddCnt) {
                    composite[mark] = true;
                    mark += p;
                }
            }
        }
        int[] mob = new int[oddCnt];
        java.util.Arrays.fill(mob, 1);
        for (int p : oddPrimes) {
            int idx = (p - 1) / 2;
            while (idx < oddCnt) {
                mob[idx] = -mob[idx];
                idx += p;
            }
            if (p <= mu / p) {
                int p2 = p * p;
                idx = (p2 - 1) / 2;
                while (idx < oddCnt) {
                    mob[idx] = 0;
                    idx += p2;
                }
            }
        }
        int[] coeff = mob.clone();
        for (int q : oddPrimes) {
            if (q % 4 != 3)
                continue;
            int nIdx = (q - 1) / 2, mIdx = 0;
            while (nIdx < oddCnt) {
                coeff[nIdx] += mob[mIdx];
                mIdx++;
                nIdx += q;
            }
        }
        long total = 0;
        for (int idx = 0; idx < oddCnt; idx++) {
            int c = coeff[idx];
            if (c == 0)
                continue;
            long u = 2L * idx + 1, u2 = u * u;
            long terms = (inc / u2 + 3) / 4;
            total += c * terms;
        }
        return String.valueOf(total);
    }

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