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

public class Euler962 {

    static int irootFloor(long x) {
        if (x <= 0)
            return 0;
        long r = (long) Math.sqrt(x);
        while ((r + 1) * (r + 1) <= x) {
            ++r;
        }
        while (r * r > x) {
            --r;
        }
        return (int) r;
    }

    static int irootCeil(long x) {
        if (x <= 0)
            return 0;
        int r = irootFloor(x);
        if ((long) r * r < x) {
            ++r;
        }
        return r;
    }

    static int cubeRootFloor(long x) {
        int lo = 0;
        int hi = (int) Math.cbrt(x) + 5;
        while ((long) hi * hi * hi <= x) {
            ++hi;
        }
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            long cube = (long) mid * mid * mid;
            if (cube <= x) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

    static int[] buildSpf(int n) {
        int[] spf = new int[n + 1];
        for (int i = 0; i <= n; ++i) {
            spf[i] = i;
        }
        for (int i = 2; (long) i * i <= n; ++i) {
            if (spf[i] != i)
                continue;
            for (int j = i * i; j <= n; j += i) {
                if (spf[j] == j) {
                    spf[j] = i;
                }
            }
        }
        return spf;
    }

    static int[] buildSquarefreeParts(int n, int[] spf) {
        int[] sf = new int[n + 1];
        Arrays.fill(sf, 1);
        sf[0] = 0;
        for (int x = 1; x <= n; ++x) {
            int t = x;
            int value = 1;
            while (t > 1) {
                int p = spf[t];
                int c = 0;
                while (t % p == 0) {
                    t /= p;
                    c ^= 1;
                }
                if (c != 0) {
                    value *= p;
                }
            }
            sf[x] = value;
        }
        return sf;
    }

    static class PrimeExp implements Comparable<PrimeExp> {
        int p;
        int e;

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

        @Override
        public int compareTo(PrimeExp o) {
            return Integer.compare(this.p, o.p);
        }
    }

    static List<List<PrimeExp>> buildFactorTable(int n, int[] spf) {
        List<List<PrimeExp>> table = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++) {
            table.add(new ArrayList<>());
        }
        for (int x = 2; x <= n; ++x) {
            int t = x;
            while (t > 1) {
                int p = spf[t];
                int e = 0;
                while (t % p == 0) {
                    t /= p;
                    ++e;
                }
                table.get(x).add(new PrimeExp(p, e));
            }
        }
        return table;
    }

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

    static long countForK(int limit, int k, int[] squarefreeU, List<List<PrimeExp>> factors) {
        int L = limit / k;
        if (L < 2)
            return 0;

        long subtotal = 0;
        int vMin = (k + 1) / 2;

        for (int v = vMin; v < k; ++v) {
            if (gcd(v, k) != 1)
                continue;

            int u = k - v;
            int sfU = squarefreeU[u];
            long W = (long) v * sfU;
            if (W > (long) L * L)
                continue;

            List<PrimeExp> wf = new ArrayList<>(factors.get(v));
            if (sfU != 1) {
                for (PrimeExp pe : factors.get(sfU)) {
                    boolean found = false;
                    for (PrimeExp existing : wf) {
                        if (existing.p == pe.p) {
                            existing.e += 1;
                            found = true;
                            break;
                        }
                    }
                    if (!found) {
                        wf.add(new PrimeExp(pe.p, 1));
                    }
                }
            }
            Collections.sort(wf);

            int rMax = (int) (((long) u * L) / (u + 2 * v));
            for (int r = 1; r <= rMax; ++r) {
                List<PrimeExp> rf = factors.get(r);

                long s0 = 1;
                int i = 0;
                int j = 0;
                boolean valid = true;

                while (i < wf.size() || j < rf.size()) {
                    int p = 0, e = 0, a = 0;

                    if (j == rf.size() || (i < wf.size() && wf.get(i).p < rf.get(j).p)) {
                        p = wf.get(i).p;
                        e = wf.get(i).e;
                        a = 0;
                        ++i;
                    } else if (i == wf.size() || rf.get(j).p < wf.get(i).p) {
                        p = rf.get(j).p;
                        e = 0;
                        a = rf.get(j).e;
                        ++j;
                    } else {
                        p = wf.get(i).p;
                        e = wf.get(i).e;
                        a = rf.get(j).e;
                        ++i;
                        ++j;
                    }

                    int b0 = (a < e) ? (e - a) : ((a - e) & 1);

                    if (b0 > 0) {
                        for (int k_idx = 0; k_idx < b0; ++k_idx) {
                            s0 *= p;
                            if (s0 > L) {
                                valid = false;
                                break;
                            }
                        }
                        if (!valid)
                            break;
                    }
                }

                if (!valid)
                    continue;

                int sMin = (int) (((long) (u + 2 * v) * r + (u - 1)) / u);
                if (sMin > L)
                    continue;

                long ratioMin = (sMin + s0 - 1) / s0;
                int nMin = irootCeil(ratioMin);
                int nMax = irootFloor(L / s0);
                if (nMin > nMax)
                    continue;

                if ((s0 & 1L) == 0) {
                    if ((r & 1) == 0) {
                        subtotal += (nMax - nMin + 1);
                    }
                    continue;
                }

                int wantParity = r & 1;
                if ((nMin & 1) != wantParity) {
                    ++nMin;
                }
                if (nMin <= nMax) {
                    subtotal += (nMax - nMin) / 2 + 1;
                }
            }
        }

        return subtotal;
    }

    static long solveFast(int limit) {
        long n2Twice = 2L * limit * limit;
        int kMax = cubeRootFloor(n2Twice) + 2;
        int maxNeeded = Math.max(kMax, limit / 6 + 5);

        int[] spf = buildSpf(maxNeeded);
        int[] squarefreeU = buildSquarefreeParts(kMax, spf);
        List<List<PrimeExp>> factors = buildFactorTable(maxNeeded, spf);

        return IntStream.rangeClosed(2, kMax)
                .parallel()
                .mapToLong(k -> countForK(limit, k, squarefreeU, factors))
                .sum();
    }

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

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