import java.util.*;

public class Euler370 {
    public static String solve() {
        long LIMIT = 25_000_000_000_000L;
        int pMax = (int) Math.sqrt(LIMIT / 3.0);
        double phi = (1.0 + Math.sqrt(5.0)) / 2.0;

        int[] spf = new int[pMax + 1];
        for (int i = 0; i <= pMax; i++)
            spf[i] = i;
        for (int i = 2; (long) i * i <= pMax; i++)
            if (spf[i] == i)
                for (int j = i * i; j <= pMax; j += i)
                    if (spf[j] == j)
                        spf[j] = i;

        long total = 0;
        for (int p = 1; p <= pMax; p++) {
            int qTriMax = qMaxTri(p, phi);
            int qNormMax = qMaxNorm(p, LIMIT);
            int qEnd = Math.min(qTriMax, qNormMax);
            if (qEnd < p)
                continue;

            int[] dprimes = distinctPrimes(p, spf);
            int nd = dprimes.length;
            int divCount = 1 << nd;
            int[] divs = new int[divCount];
            int[] mus = new int[divCount];
            for (int mask = 0; mask < divCount; mask++) {
                int d = 1, mu = 1;
                for (int i = 0; i < nd; i++)
                    if ((mask & (1 << i)) != 0) {
                        d *= dprimes[i];
                        mu = -mu;
                    }
                divs[mask] = d;
                mus[mask] = mu;
            }

            int left = p;
            while (left <= qEnd) {
                long normLeft = (long) left * left + (long) p * left + (long) p * p;
                long quotient = LIMIT / normLeft;
                if (quotient == 0)
                    break;
                long normLim = LIMIT / quotient;
                int right = Math.min(qEnd, qMaxNorm(p, normLim));

                int cop;
                int span = right - left + 1;
                if (span <= 8) {
                    cop = 0;
                    for (int q = left; q <= right; q++)
                        if (gcd(p, q) == 1)
                            cop++;
                } else {
                    cop = 0;
                    for (int i = 0; i < divCount; i++)
                        cop += mus[i] * (right / divs[i] - (left - 1) / divs[i]);
                }
                total += cop * quotient;
                left = right + 1;
            }
        }
        return String.valueOf(total);
    }

    static int gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    static int qMaxTri(int p, double phi) {
        int q = (int) (phi * p);
        while (q > 0 && (long) q * q >= (long) p * p + (long) p * q)
            q--;
        while ((long) (q + 1) * (q + 1) < (long) p * p + (long) p * (q + 1))
            q++;
        return q;
    }

    static int qMaxNorm(int p, long limit) {
        if (3L * p * p > limit)
            return 0;
        long disc = 4 * limit - 3L * p * p;
        long root = (long) Math.sqrt((double) disc);
        while ((root + 1) * (root + 1) <= disc)
            root++;
        while (root * root > disc)
            root--;
        int q = (int) ((root - p) / 2);
        if (q < 0)
            q = 0;
        while (q > 0 && (long) q * q + (long) p * q + (long) p * p > limit)
            q--;
        while ((long) (q + 1) * (q + 1) + (long) p * (q + 1) + (long) p * p <= limit)
            q++;
        return q;
    }

    static int[] distinctPrimes(int val, int[] spf) {
        List<Integer> ps = new ArrayList<>();
        while (val > 1) {
            int p = spf[val];
            ps.add(p);
            while (val % p == 0)
                val /= p;
        }
        return ps.stream().mapToInt(Integer::intValue).toArray();
    }

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