import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Euler998 {
    private static final int TARGET = 1_000_000;
    private static final double HALF_PI = Math.PI / 2.0;

    private static final class Leg {
        final int offset;
        final int hypotenuse;

        Leg(int offset, int hypotenuse) {
            this.offset = offset;
            this.hypotenuse = hypotenuse;
        }
    }

    private static final class WidthState {
        final double width;
        final int uMin;
        final int uMax;
        final int vMin;
        final int vMax;

        WidthState(double width, int uMin, int uMax, int vMin, int vMax) {
            this.width = width;
            this.uMin = uMin;
            this.uMax = uMax;
            this.vMin = vMin;
            this.vMax = vMax;
        }
    }

    private static long isqrt(long n) {
        long r = (long) Math.sqrt((double) n);
        while ((r + 1) * (r + 1) <= n) {
            ++r;
        }
        while (r * r > n) {
            --r;
        }
        return r;
    }

    private static long isSquare(long n) {
        long root = isqrt(n);
        return root * root == n ? root : -1;
    }

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

    private static double normalizeAngle(double angle) {
        angle = angle % HALF_PI;
        if (angle < 0.0) {
            angle += HALF_PI;
        }
        if (angle < 1e-18 || HALF_PI - angle < 1e-18) {
            return 0.0;
        }
        return angle;
    }

    private static WidthState evaluate(double[][] points, double angle) {
        double co = Math.cos(angle);
        double si = Math.sin(angle);
        double[] u = new double[3];
        double[] v = new double[3];
        for (int i = 0; i < 3; ++i) {
            u[i] = points[i][0] * co + points[i][1] * si;
            v[i] = -points[i][0] * si + points[i][1] * co;
        }

        int uMin = 0;
        int uMax = 0;
        int vMin = 0;
        int vMax = 0;
        for (int i = 1; i < 3; ++i) {
            if (u[i] < u[uMin]) {
                uMin = i;
            }
            if (u[i] > u[uMax]) {
                uMax = i;
            }
            if (v[i] < v[vMin]) {
                vMin = i;
            }
            if (v[i] > v[vMax]) {
                vMax = i;
            }
        }

        double width = Math.max(u[uMax] - u[uMin], v[vMax] - v[vMin]);
        return new WidthState(width, uMin, uMax, vMin, vMax);
    }

    private static double minimumSquare(int a, int b, int c) {
        if (a > b) {
            int t = a;
            a = b;
            b = t;
        }
        if (b > c) {
            int t = b;
            b = c;
            c = t;
        }
        if (a > b) {
            int t = a;
            a = b;
            b = t;
        }

        double x = ((double) a * a + (double) c * c - (double) b * b) / (2.0 * c);
        double y2 = (double) a * a - x * x;
        if (y2 < 0.0 && y2 > -1e-12) {
            y2 = 0.0;
        }
        double y = Math.sqrt(y2);
        double[][] points = {
            {0.0, 0.0},
            {(double) c, 0.0},
            {x, y}
        };

        List<Double> angles = new ArrayList<>();
        angles.add(0.0);
        for (int i = 0; i < 3; ++i) {
            for (int j = i + 1; j < 3; ++j) {
                double edge = Math.atan2(points[j][1] - points[i][1], points[j][0] - points[i][0]);
                angles.add(normalizeAngle(edge));
                angles.add(normalizeAngle(edge + HALF_PI));
            }
        }

        Collections.sort(angles);
        List<Double> boundaries = new ArrayList<>();
        for (double angle : angles) {
            if (boundaries.isEmpty() || Math.abs(angle - boundaries.get(boundaries.size() - 1)) > 1e-15) {
                boundaries.add(angle);
            }
        }

        List<Double> candidates = new ArrayList<>(boundaries);
        List<Double> endpoints = new ArrayList<>(boundaries);
        endpoints.add(HALF_PI);
        for (int i = 0; i + 1 < endpoints.size(); ++i) {
            double lo = endpoints.get(i);
            double hi = endpoints.get(i + 1);
            if (hi - lo < 1e-15) {
                continue;
            }

            WidthState state = evaluate(points, (lo + hi) / 2.0);
            double ax = points[state.uMax][0] - points[state.uMin][0];
            double ay = points[state.uMax][1] - points[state.uMin][1];
            double bx = points[state.vMax][0] - points[state.vMin][0];
            double by = points[state.vMax][1] - points[state.vMin][1];
            double left = ax - by;
            double right = ay + bx;
            if (Math.abs(right) < 1e-18) {
                continue;
            }

            double root = Math.atan2(-left, right);
            for (double angle : new double[] {root, root + Math.PI}) {
                double current = normalizeAngle(angle);
                if (lo + 1e-15 < current && current < hi - 1e-15) {
                    candidates.add(current);
                }
            }
        }

        double best = Double.MAX_VALUE;
        for (double angle : candidates) {
            best = Math.min(best, evaluate(points, angle).width);
        }
        return best;
    }

    private static long triangleKey(int a, int b, int c) {
        if (a > b) {
            int t = a;
            a = b;
            b = t;
        }
        if (b > c) {
            int t = b;
            b = c;
            c = t;
        }
        if (a > b) {
            int t = a;
            a = b;
            b = t;
        }
        return ((long) a << 42) | ((long) b << 21) | (long) c;
    }

    @SuppressWarnings("unchecked")
    private static List<Leg>[] pythagoreanOffsets(int limit) {
        List<Leg>[] bySide = new ArrayList[limit + 1];
        for (int i = 0; i <= limit; ++i) {
            bySide[i] = new ArrayList<>();
        }

        int bound = (int) isqrt(2L * limit) + 2;
        for (int m = 2; m <= bound; ++m) {
            for (int n = 1; n < m; ++n) {
                if (((m - n) & 1) == 0 || gcd(m, n) != 1) {
                    continue;
                }

                int a = m * m - n * n;
                int b = 2 * m * n;
                int c = m * m + n * n;

                int[] sides = {a, b};
                int[] offsets = {b, a};
                for (int idx = 0; idx < 2; ++idx) {
                    int side0 = sides[idx];
                    int offset0 = offsets[idx];
                    int side = side0;
                    int offset = offset0;
                    int hypotenuse = c;
                    while (side <= limit) {
                        if (offset <= side) {
                            bySide[side].add(new Leg(offset, hypotenuse));
                        }
                        side += side0;
                        offset += offset0;
                        hypotenuse += c;
                    }
                }
            }
        }

        Comparator<Leg> cmp = Comparator.comparingInt((Leg leg) -> leg.offset)
                                        .thenComparingInt(leg -> leg.hypotenuse);
        for (int side = 0; side <= limit; ++side) {
            List<Leg> legs = bySide[side];
            if (legs.isEmpty()) {
                continue;
            }
            legs.sort(cmp);
            List<Leg> unique = new ArrayList<>();
            Leg prev = null;
            for (Leg leg : legs) {
                if (prev == null || prev.offset != leg.offset || prev.hypotenuse != leg.hypotenuse) {
                    unique.add(leg);
                    prev = leg;
                }
            }
            bySide[side] = unique;
        }

        return bySide;
    }

    private static long solve(int limit) {
        List<Leg>[] legs = pythagoreanOffsets(limit);
        Set<Long> seen = new HashSet<>();
        long total = 0;

        for (int side = 1; side <= limit; ++side) {
            List<Leg> current = legs[side];
            for (int i = 0; i < current.size(); ++i) {
                long p = current.get(i).offset;
                int hypI = current.get(i).hypotenuse;
                for (int j = i; j < current.size(); ++j) {
                    long q = current.get(j).offset;
                    int hypJ = current.get(j).hypotenuse;
                    long base = p + q;
                    if (base <= side && p * q >= (long) side * (side - base)) {
                        long key = triangleKey((int) base, hypI, hypJ);
                        if (seen.add(key)) {
                            total += base + hypI + hypJ;
                        }
                    }

                    long u = side - p;
                    long v = side - q;
                    if (u > 0 && v > 0) {
                        long third = isSquare(u * u + v * v);
                        if (third >= 0 && minimumSquare(hypI, hypJ, (int) third) + 1e-6 >= side) {
                            long key = triangleKey(hypI, hypJ, (int) third);
                            if (seen.add(key)) {
                                total += hypI + hypJ + third;
                            }
                        }
                    }
                }
            }
        }

        return total;
    }

    private static void check(long actual, long expected, String label) {
        if (actual != expected) {
            throw new IllegalStateException(label + ": expected " + expected + ", got " + actual);
        }
    }

    private static void runCheckpoints() {
        check(solve(40), 346L, "T(40)");
        check(solve(400), 76_402L, "T(400)");
        check(solve(2_000), 3_237_036L, "T(2000)");
    }

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