import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.LongStream;

public class Euler397 {
    static long floorDiv(long a, long b) {
        if (a >= 0)
            return a / b;
        return -(((-a) + b - 1) / b);
    }

    static long countInterval(long lo, long hi) {
        if (lo > hi)
            return 0;
        return hi - lo + 1;
    }

    static long countAngleA(long u, long v, long xBound) {
        long lo = Math.max(-xBound, v - xBound);
        long hi = Math.min(xBound, Math.min(u + xBound, floorDiv(u - 1, 2)));
        return countInterval(lo, hi);
    }

    static long countAngleB(long u, long v, long xBound) {
        long lo = Math.max(-xBound, Math.max(v - xBound, floorDiv(u, 2) + 1));
        long hi = Math.min(xBound, Math.min(u + xBound, floorDiv(v - 1, 2)));
        return countInterval(lo, hi);
    }

    static long countAngleC(long u, long v, long xBound) {
        long lo = Math.max(-xBound, Math.max(v - xBound, floorDiv(v, 2) + 1));
        long hi = Math.min(xBound, u + xBound);
        return countInterval(lo, hi);
    }

    static boolean validTriangle(long s1, long s2, long s3, long xBound) {
        if (!(s1 < s2 && s2 < s3))
            return false;
        long parity = s1 + s2 + s3;
        if ((parity & 1) != 0)
            return false;

        long a = (s1 + s2 - s3) / 2;
        long b = (s1 + s3 - s2) / 2;
        long c = (s2 + s3 - s1) / 2;

        if (a < -xBound || a > xBound)
            return false;
        if (b < -xBound || b > xBound)
            return false;
        if (c < -xBound || c > xBound)
            return false;

        return a < b && b < c;
    }

    static class Factor {
        long p;
        int e;

        Factor(long p, int e) {
            this.p = p;
            this.e = e;
        }
    }

    static class Pair implements Comparable<Pair> {
        long first, second;

        Pair(long f, long s) {
            first = f;
            second = s;
        }

        @Override
        public int compareTo(Pair o) {
            if (this.first != o.first)
                return Long.compare(this.first, o.first);
            return Long.compare(this.second, o.second);
        }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof Pair))
                return false;
            Pair p = (Pair) o;
            return this.first == p.first && this.second == p.second;
        }

        @Override
        public int hashCode() {
            return Long.hashCode(first) ^ Long.hashCode(second);
        }
    }

    static void getDivisors(List<Factor> factors, int idx, long current, List<Long> result) {
        if (idx == factors.size()) {
            result.add(current);
            return;
        }
        long p = factors.get(idx).p;
        int exp = factors.get(idx).e;
        long val = current;
        for (int i = 0; i <= exp; i++) {
            getDivisors(factors, idx + 1, val, result);
            if (i != exp)
                val *= p;
        }
    }

    static long solveForK(long k, long xBound, int[] spf) {
        long n_k = k;
        int exp2 = 0;
        while ((n_k & 1) == 0) {
            exp2++;
            n_k >>= 1;
        }

        List<Factor> factors = new ArrayList<>();
        factors.add(new Factor(2, 2 * exp2 + 1));

        while (n_k > 1) {
            int p = spf[(int) n_k];
            int expP = 0;
            while (n_k % p == 0) {
                n_k /= p;
                expP++;
            }
            factors.add(new Factor(p, 2 * expP));
        }

        List<Long> divisors = new ArrayList<>();
        getDivisors(factors, 0, 1L, divisors);

        long kk = k;
        long nVal = 2 * k * k;
        long sumBound = 2 * xBound;

        List<Pair> plusOut = new ArrayList<>();
        List<Pair> minusOut = new ArrayList<>();

        for (long d : divisors) {
            for (int sign : new int[] { -1, 1 }) {
                long p = sign * d;
                long q = -nVal / p;

                long uPlus = p + kk;
                long vPlus = q - kk;
                if (uPlus < vPlus && uPlus >= -sumBound && uPlus <= sumBound && vPlus >= -sumBound
                        && vPlus <= sumBound) {
                    plusOut.add(new Pair(uPlus, vPlus));
                }

                long uMinus = p - kk;
                long vMinus = q + kk;
                if (uMinus < vMinus && uMinus >= -sumBound && uMinus <= sumBound && vMinus >= -sumBound
                        && vMinus <= sumBound) {
                    minusOut.add(new Pair(uMinus, vMinus));
                }
            }
        }

        Collections.sort(plusOut);
        List<Pair> plusOutUnique = new ArrayList<>();
        if (!plusOut.isEmpty()) {
            plusOutUnique.add(plusOut.get(0));
            for (int i = 1; i < plusOut.size(); i++) {
                if (!plusOut.get(i).equals(plusOutUnique.get(plusOutUnique.size() - 1))) {
                    plusOutUnique.add(plusOut.get(i));
                }
            }
        }
        plusOut = plusOutUnique;

        Collections.sort(minusOut);
        List<Pair> minusOutUnique = new ArrayList<>();
        if (!minusOut.isEmpty()) {
            minusOutUnique.add(minusOut.get(0));
            for (int i = 1; i < minusOut.size(); i++) {
                if (!minusOut.get(i).equals(minusOutUnique.get(minusOutUnique.size() - 1))) {
                    minusOutUnique.add(minusOut.get(i));
                }
            }
        }
        minusOut = minusOutUnique;

        List<Pair> plusIn = new ArrayList<>(plusOut.size());
        for (Pair p : plusOut)
            plusIn.add(new Pair(p.second, p.first));
        Collections.sort(plusIn);

        List<Pair> minusIn = new ArrayList<>(minusOut.size());
        for (Pair p : minusOut)
            minusIn.add(new Pair(p.second, p.first));
        Collections.sort(minusIn);

        long countA = 0, countB = 0, countC = 0;
        for (Pair p : plusOut) {
            countA += countAngleA(p.first, p.second, xBound);
            countC += countAngleC(p.first, p.second, xBound);
        }
        for (Pair p : minusOut) {
            countB += countAngleB(p.first, p.second, xBound);
        }

        long overlapAB = 0;
        int i = 0, j = 0;
        while (i < plusOut.size() && j < minusOut.size()) {
            long keyP = plusOut.get(i).first;
            long keyM = minusOut.get(j).first;
            if (keyP < keyM)
                i++;
            else if (keyM < keyP)
                j++;
            else {
                long x = keyP;
                long y = plusOut.get(i).second;
                long z = minusOut.get(j).second;
                if (validTriangle(x, y, z, xBound))
                    overlapAB++;
                i++;
                j++;
            }
        }

        long overlapAC = 0;
        i = 0;
        j = 0;
        while (i < plusIn.size() && j < plusOut.size()) {
            long keyIn = plusIn.get(i).first;
            long keyOut = plusOut.get(j).first;
            if (keyIn < keyOut)
                i++;
            else if (keyOut < keyIn)
                j++;
            else {
                long y = keyIn;
                long x = plusIn.get(i).second;
                long z = plusOut.get(j).second;
                if (validTriangle(x, y, z, xBound))
                    overlapAC++;
                i++;
                j++;
            }
        }

        long overlapBC = 0;
        i = 0;
        j = 0;
        while (i < plusIn.size() && j < minusIn.size()) {
            long keyP = plusIn.get(i).first;
            long keyM = minusIn.get(j).first;
            if (keyP < keyM)
                i++;
            else if (keyM < keyP)
                j++;
            else {
                long z = keyP;
                long y = plusIn.get(i).second;
                long x = minusIn.get(j).second;
                if (validTriangle(x, y, z, xBound))
                    overlapBC++;
                i++;
                j++;
            }
        }

        return countA + countB + countC - overlapAB - overlapAC - overlapBC;
    }

    static String solve() {
        long kLimit = 1000000L;
        long xBound = 1000000000L;

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

        long total = LongStream.rangeClosed(1, kLimit)
                .parallel()
                .map(k -> solveForK(k, xBound, spf))
                .sum();

        return Long.toString(total);
    }

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