import java.util.ArrayList;

public class Euler846 {

    static class GcdResult {
        long gcd;
        long coeffA;
        long coeffB;

        GcdResult(long g, long a, long b) {
            gcd = g;
            coeffA = a;
            coeffB = b;
        }
    }

    static GcdResult extendedGcd(long a, long b) {
        long x = a, y = b;
        long ax = 1, ay = 0;
        long bx = 0, by = 1;
        while (x != 0) {
            long k = y / x;
            long temp = y % x;
            y = x;
            x = temp;

            temp = ay - k * ax;
            ay = ax;
            ax = temp;

            temp = by - k * bx;
            by = bx;
            bx = temp;
        }
        return new GcdResult(y, ay, by);
    }

    static class GaussianInt {
        long x, y;

        GaussianInt(long x, long y) {
            this.x = x;
            this.y = y;
        }

        GaussianInt mul(GaussianInt o) {
            return new GaussianInt(this.x * o.x - this.y * o.y, this.x * o.y + this.y * o.x);
        }

        long norm() {
            return x * x + y * y;
        }
    }

    static GaussianInt normalize(GaussianInt a) {
        long ax = Math.abs(a.x);
        long ay = Math.abs(a.y);
        if (ax < ay) {
            long tmp = ax;
            ax = ay;
            ay = tmp;
        }
        return new GaussianInt(ax, ay);
    }

    static long solveF(int N) {
        ArrayList<Integer> primes = new ArrayList<>(N / 2);
        int[] spf = new int[N + 1];

        for (int i = 2; i <= N; ++i) {
            if (spf[i] == 0) {
                spf[i] = i;
                primes.add(i);
            }
            for (int p : primes) {
                if ((long) p * i > N)
                    break;
                spf[p * i] = p;
                if (p == spf[i])
                    break;
            }
        }

        int[] exactSqrt = new int[N + 1];
        for (int i = 1; (long) i * i <= N; ++i) {
            exactSqrt[i * i] = i;
        }

        GaussianInt[] vals = new GaussianInt[N + 1];
        vals[1] = new GaussianInt(1, 0);
        if (N >= 2)
            vals[2] = new GaussianInt(1, 1);

        for (int p : primes) {
            if (p == 2 || (p & 3) == 3)
                continue;

            long a = 0, b = 0;
            for (int i = 1;; ++i) {
                int rem = p - i * i;
                if (rem >= 0 && exactSqrt[rem] != 0) {
                    a = i;
                    b = exactSqrt[rem];
                    break;
                }
            }

            GaussianInt cur = new GaussianInt(1, 0);
            for (int q = 1; (long) q * p <= N;) {
                q *= p;
                cur = cur.mul(new GaussianInt(a, b));
                vals[q] = normalize(cur);
                if (2 * q <= N) {
                    vals[2 * q] = normalize(cur.mul(new GaussianInt(1, 1)));
                }
            }
        }

        ArrayList<ArrayList<Integer>> parents = new ArrayList<>(N + 1);
        ArrayList<ArrayList<long[]>> dp = new ArrayList<>(N + 1);
        for (int i = 0; i <= N; ++i) {
            parents.add(new ArrayList<>());
            dp.add(new ArrayList<>());
        }

        for (int i = 1; i <= N; ++i) {
            if (vals[i] == null)
                continue;
            if (i == 1)
                continue;

            GaussianInt v = vals[i];
            GcdResult gcdRes = extendedGcd(v.x, v.y);
            long g = gcdRes.gcd;
            long cx = gcdRes.coeffA;
            long cy = gcdRes.coeffB;

            if (g < 0) {
                g = -g;
                cx = -cx;
                cy = -cy;
            }

            GaussianInt p1 = new GaussianInt(Math.abs(cy), Math.abs(cx));
            GaussianInt p2 = new GaussianInt(v.x - p1.x, v.y - p1.y);
            if (p1.norm() > p2.norm()) {
                GaussianInt tmp = p1;
                p1 = p2;
                p2 = tmp;
            }

            int n1 = (int) p1.norm();
            if (n1 <= N && vals[n1] != null) {
                parents.get(i).add(n1);
            }

            int n2 = (int) p2.norm();
            if (i > 2 && n2 <= N && vals[n2] != null) {
                parents.get(i).add(n2);
            }

            for (int z = 0; z < parents.get(i).size(); ++z) {
                dp.get(i).add(new long[] { 0, 0 });
            }
        }

        long answer = 0;

        for (int i = N; i >= 1; --i) {
            ArrayList<Integer> pi = parents.get(i);
            ArrayList<long[]> dpi = dp.get(i);

            for (int z = 0; z < pi.size(); ++z) {
                long curWays = dpi.get(z)[0];
                long curSum = dpi.get(z)[1];
                answer += curWays * (i + pi.get(z)) + curSum;
                dpi.get(z)[0]++;
            }

            if (pi.size() == 2) {
                int j = pi.get(1);
                ArrayList<Integer> pj = parents.get(j);
                int z = pj.indexOf(pi.get(0));

                long w0 = dpi.get(0)[0], s0 = dpi.get(0)[1];
                long w1 = dpi.get(1)[0], s1 = dpi.get(1)[1];

                long[] dpjz = dp.get(j).get(z);
                dpjz[0] += w0 * w1;
                dpjz[1] += w0 * w1 * i + w0 * s1 + w1 * s0;
            }
        }

        return answer;
    }

    public static String solve() {
        return Long.toString(solveF(1000000));
    }

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