import java.util.HashMap;
import java.util.Map;

public class Euler513 {

    static Map<Long, Long> memoF = new HashMap<>();

    static long floorDiv(long a, long b) {
        return Math.floorDiv(a, b);
    }

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

    static long pointsInTrapezoid(long slope, long intercept, long denominator, long lowerDomain, long upperDomain,
            boolean boundary) {
        long result = 0;
        while (true) {
            if (Math.abs(upperDomain - lowerDomain) <= 8) {
                long s = 0;
                long adjustment = boundary ? 0 : 1;
                if (upperDomain > lowerDomain) {
                    for (long x = lowerDomain + 1; x <= upperDomain; x++) {
                        s += floorDiv(slope * x + intercept - adjustment, denominator);
                    }
                } else {
                    for (long x = upperDomain + 1; x <= lowerDomain; x++) {
                        s += floorDiv(slope * x + intercept - adjustment, denominator);
                    }
                    s = -s;
                }
                result += s;
                break;
            }

            result += (upperDomain - lowerDomain) * floorDiv(intercept, denominator);
            intercept = ((intercept % denominator) + denominator) % denominator;

            result += ((upperDomain - lowerDomain) * (upperDomain + lowerDomain + 1) / 2)
                    * floorDiv(slope, denominator);
            slope = ((slope % denominator) + denominator) % denominator;

            if (slope != 0) {
                long upperValue = floorDiv(slope * upperDomain + intercept, denominator);
                long lowerValue = floorDiv(slope * lowerDomain + intercept, denominator);
                result += upperDomain * upperValue - lowerDomain * lowerValue;
                lowerDomain = upperValue;
                upperDomain = lowerValue;
                long tmp = slope;
                slope = denominator;
                denominator = tmp;
                intercept = -intercept;
                boundary = !boundary;
            } else {
                if (intercept == 0 && !boundary)
                    result -= upperDomain - lowerDomain;
                break;
            }
        }
        return result;
    }

    static long pointsInTrapezoidMod2(long slope, long intercept, long denominator, long lowerDomain, long upperDomain,
            boolean boundary, long xResidue, long yResidue) {
        if ((yResidue & 1) != 0)
            intercept += denominator;
        if ((xResidue & 1) != 0) {
            intercept -= slope;
            lowerDomain++;
            upperDomain++;
        }
        return pointsInTrapezoid(2 * slope, intercept, 2 * denominator, floorDiv(lowerDomain, 2),
                floorDiv(upperDomain, 2), boundary);
    }

    static long fValue(long n) {
        long result = 0;
        long threeHalvesN = n + n / 2;
        long root = isqrtFloor(threeHalvesN);
        int[][] ij = { { 0, 1 }, { 1, 0 }, { 1, 1 } };

        for (int[] pair : ij) {
            long i = pair[0];
            long j = pair[1];

            long maxT = 1;
            for (long s = 2; s < root; s++) {
                if (3 * (maxT + 1) * (maxT + 1) <= s * s)
                    maxT++;
                if (i == j || (s & 1) == 0) {
                    for (long t = ((s - 1) & 1) + 1; t <= maxT; t += 2) {
                        long vMid = t * n / ((s - t) * (s + t));
                        long vMax = n * (s + t) / (s * s + 2 * s * t - t * t);
                        result += pointsInTrapezoidMod2(s, 0, t, 0, vMid, true, j, i);
                        result += pointsInTrapezoidMod2(t, n, s, vMid, vMax, true, j, i);
                        result -= pointsInTrapezoidMod2(s + 3 * t, 0, s + t, 0, vMax, false, j, i);
                    }
                }
            }

            long uMax = threeHalvesN / root;
            for (long u = 1 + ((i + 1) & 1); u <= uMax; u += 2) {
                long vMaxOuter = Math.min(n / 2, u - 1);
                for (long v = 1 + ((j + 1) & 1); v <= vMaxOuter; v += 2) {
                    long midS = (v + n) / u;
                    int residueCount = (i == j ? 2 : 1);
                    for (int sr = 0; sr < residueCount; sr++) {
                        long sResidue = (i == j ? sr : 0);

                        long minS = 0, maxS = -1;
                        long slope0 = 0, slope1 = 1;
                        if (u * u < 3 * v * v) {
                            minS = root;
                            maxS = n * (3 * v - u) / (2 * u * v + v * v - u * u);
                            slope0 = u - v;
                            slope1 = 3 * v - u;
                        } else {
                            minS = Math.max(root, floorDiv(u + v - 1, v));
                            maxS = n * u / ((u - v) * (u + v));
                            slope0 = v;
                            slope1 = u;
                        }

                        if (maxS >= minS) {
                            result += pointsInTrapezoidMod2(slope0, 0, slope1, minS - 1, maxS, true, sResidue,
                                    sResidue);
                            if (midS < maxS) {
                                result -= pointsInTrapezoidMod2(u, -n, v, Math.max(midS, minS - 1), maxS, false,
                                        sResidue, sResidue);
                            }
                        }
                    }
                }
            }
        }
        return result;
    }

    static long F(long n) {
        if (n <= 0)
            return 0;
        if (memoF.containsKey(n))
            return memoF.get(n);

        long result = fValue(n);
        long k = 3;
        long nOverK = n / k;
        while (k <= nOverK) {
            result -= F(nOverK);
            k += 2;
            nOverK = n / k;
        }

        long minK = (nOverK + 1 > 0) ? n / (nOverK + 1) : n;
        while (nOverK > 0) {
            long maxK = n / nOverK;
            long left = (minK + 1) + (minK & 1);
            long right = maxK - ((maxK + 1) & 1);
            long count = 0;
            if (right >= left)
                count = (right - left) / 2 + 1;
            result -= F(nOverK) * count;
            nOverK--;
            minK = maxK;
        }

        memoF.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        long n = 100000;
        System.out.println(F(n));
    }
}