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

public class Euler450 {

    static BigInteger gcdBig(BigInteger a, BigInteger b) {
        a = a.abs();
        b = b.abs();
        while (!b.equals(BigInteger.ZERO)) {
            BigInteger t = a.remainder(b);
            a = b;
            b = t;
        }
        return a;
    }

    static BigInteger[] powGauss(BigInteger x, BigInteger y, int n) {
        BigInteger rx = BigInteger.ONE, ry = BigInteger.ZERO;
        for (int i = 0; i < n; i++) {
            BigInteger nx = rx.multiply(x).subtract(ry.multiply(y));
            BigInteger ny = rx.multiply(y).add(ry.multiply(x));
            rx = nx;
            ry = ny;
        }
        return new BigInteger[] { rx, ry };
    }

    static BigInteger triBig(long n) {
        return BigInteger.valueOf(n).multiply(BigInteger.valueOf(n + 1)).divide(BigInteger.valueOf(2));
    }

    static class DenomResult {
        long den;
        BigInteger ux, uy, g0;

        DenomResult(long den, BigInteger ux, BigInteger uy, BigInteger g0) {
            this.den = den;
            this.ux = ux;
            this.uy = uy;
            this.g0 = g0;
        }
    }

    static DenomResult denomRequired(int p, int q, int A, int B, int D) {
        int e = p - q;
        BigInteger[] aq = powGauss(BigInteger.valueOf(A), BigInteger.valueOf(B), q);
        BigInteger[] aec = powGauss(BigInteger.valueOf(A), BigInteger.valueOf(-B), e);

        BigInteger Deq = BigInteger.valueOf(D).pow(e - q);
        BigInteger ux = BigInteger.valueOf(e).multiply(aq[0]).multiply(Deq).add(BigInteger.valueOf(q).multiply(aec[0]));
        BigInteger uy = BigInteger.valueOf(e).multiply(aq[1]).multiply(Deq).add(BigInteger.valueOf(q).multiply(aec[1]));

        BigInteger De = BigInteger.valueOf(D).pow(e);
        BigInteger g0 = gcdBig(gcdBig(De, ux), uy);

        BigInteger denBig = De.divide(g0);
        return new DenomResult(denBig.longValue(), ux, uy, g0);
    }

    static int[][] variations(int a, int b) {
        return new int[][] {
                { a, b }, { a, -b }, { -a, b }, { -a, -b },
                { b, a }, { b, -a }, { -b, a }, { -b, -a }
        };
    }

    static class Triple {
        int a, b, c;

        Triple(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }
    }

    static List<Triple> primitiveTriples(int Cmax) {
        List<Triple> out = new ArrayList<>();
        int mlim = (int) Math.sqrt(Cmax) + 2;
        for (int m = 2; m <= mlim; m++) {
            for (int n = 1; n < m; n++) {
                if (((m - n) & 1) == 0)
                    continue;
                if (gcdInt(m, n) != 1)
                    continue;
                int a = m * m - n * n;
                int b = 2 * m * n;
                int c = m * m + n * n;
                if (c > Cmax)
                    continue;
                out.add(new Triple(a, b, c));
            }
        }
        return out;
    }

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

    static class SieveResult {
        byte[] mu;
        int[] phi;
    }

    static SieveResult sieveMuPhi(int N) {
        SieveResult res = new SieveResult();
        res.mu = new byte[N + 1];
        res.phi = new int[N + 1];
        boolean[] comp = new boolean[N + 1];
        List<Integer> primes = new ArrayList<>();

        res.mu[1] = 1;
        res.phi[1] = 1;

        for (int i = 2; i <= N; i++) {
            if (!comp[i]) {
                primes.add(i);
                res.phi[i] = i - 1;
                res.mu[i] = -1;
            }
            for (int p : primes) {
                long v = (long) i * p;
                if (v > N)
                    break;
                comp[(int) v] = true;
                if (i % p == 0) {
                    res.phi[(int) v] = res.phi[i] * p;
                    res.mu[(int) v] = 0;
                    break;
                } else {
                    res.phi[(int) v] = res.phi[i] * (p - 1);
                    res.mu[(int) v] = (byte) -res.mu[i];
                }
            }
        }
        return res;
    }

    static long[] computeBParallel(int N, byte[] mu) {
        int threads = Math.max(1, Math.min(8, Runtime.getRuntime().availableProcessors()));

        long[][] local = new long[threads][N + 1];
        int block = N / threads;

        IntStream.range(0, threads).parallel().forEach(t -> {
            int start = (t == 0) ? 1 : t * block + 1;
            int end = (t == threads - 1) ? N : (t + 1) * block;

            for (int d = start; d <= end; d++) {
                int md = mu[d];
                if (md == 0)
                    continue;
                long coef = (long) md * d;
                for (int p = d; p <= N; p += d) {
                    long m = (p - 1) / (2L * d);
                    local[t][p] += coef * (m * (m + 1) / 2);
                }
            }
        });

        long[] B = new long[N + 1];
        for (int p = 1; p <= N; p++) {
            long s = 0;
            for (int t = 0; t < threads; t++) {
                s += local[t][p];
            }
            B[p] = s;
        }

        return B;
    }

    public static String solve() {
        int N = 1000000;
        SieveResult sieve = sieveMuPhi(N);
        long[] B = computeBParallel(N, sieve.mu);

        BigInteger total = BigInteger.ZERO;

        for (int p = 3; p <= N; p++) {
            long A = sieve.phi[p] / 2;
            if (A == 0)
                continue;
            long Bsum = B[p];

            long inner;
            if ((p & 1) != 0) {
                inner = 4L * p * A - 2L * Bsum;
            } else {
                if (p % 4 == 0) {
                    inner = 4L * p * A;
                } else {
                    inner = 4L * p * A - 4L * Bsum;
                }
            }

            long M = N / p;
            total = total.add(BigInteger.valueOf(inner).multiply(triBig(M)));
        }

        int Dmax = (int) Math.sqrt(N / 3) + 2;
        List<Triple> triples = primitiveTriples(Dmax);

        int maxPextra = 12;

        for (int p = 3; p <= Math.min(N, maxPextra); p++) {
            long M = N / p;
            for (int q = 1; 2 * q < p; q++) {
                if (gcdInt(p, q) != 1)
                    continue;

                for (Triple t : triples) {
                    int[][] vars = variations(t.a, t.b);
                    for (int[] var : vars) {
                        DenomResult dr = denomRequired(p, q, var[0], var[1], t.c);
                        if (dr.den > M)
                            continue;

                        BigInteger bx = dr.ux.divide(dr.g0);
                        BigInteger by = dr.uy.divide(dr.g0);
                        BigInteger baseAbs = bx.abs().add(by.abs());

                        long mmax = M / dr.den;
                        total = total.add(baseAbs.multiply(triBig(mmax)));
                    }
                }
            }
        }

        return total.toString();
    }

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