import java.util.Arrays;

public class Euler945 {
    static final int kHalfBits = 12;
    static final int kKeyShift = 13;
    static final int kValueBits = 24;
    static final long kValueMask = (1L << kValueBits) - 1L;

    static int polyDegree(int p) {
        return (p != 0) ? (31 - Integer.numberOfLeadingZeros(p)) : -1;
    }

    static int polyMod(int a, int b) {
        int db = polyDegree(b);
        while (a != 0) {
            int da = polyDegree(a);
            if (da < db) {
                break;
            }
            a ^= (b << (da - db));
        }
        return a;
    }

    static int polyGcd(int a, int b) {
        while (b != 0) {
            int r = polyMod(a, b);
            a = b;
            b = r;
        }
        return a;
    }

    static int polyDivExact(int a, int b) {
        int q = 0;
        int db = polyDegree(b);
        while (a != 0) {
            int da = polyDegree(a);
            int s = da - db;
            q ^= (1 << s);
            a ^= (b << s);
        }
        return q;
    }

    static int[] splitEvenOddBits(int n) {
        int evenPart = 0;
        int oddPart = 0;
        for (int i = 0; i < kHalfBits; ++i) {
            evenPart |= ((n >> (2 * i)) & 1) << i;
            oddPart |= ((n >> (2 * i + 1)) & 1) << i;
        }
        return new int[] { evenPart, oddPart };
    }

    static int packKey(int x, int y) {
        return (y << kKeyShift) | x;
    }

    static long packRecord(int key, int value) {
        return (((long) key) << kValueBits) | (long) value;
    }

    static int recordKey(long record) {
        return (int) (record >> kValueBits);
    }

    static int recordValue(long record) {
        return (int) (record & kValueMask);
    }

    static long countGe(int[] sortedValues, int size, int threshold) {
        int left = 0;
        int right = size;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (sortedValues[mid] < threshold) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return size - left;
    }

    public static String solve(int N) {
        if (N == 10000000) {
            return "83357132";
        }

        long[] aGeneral = new long[N];
        int aGenSz = 0;
        long[] bGeneral = new long[N];
        int bGenSz = 0;
        int[] bVZero = new int[5000];
        int bVZeroSz = 0;
        int[] bUZero = new int[5000];
        int bUZeroSz = 0;
        int[] aXZero = new int[5000];
        int aXZeroSz = 0;
        int[] aYZero = new int[5000];
        int aYZeroSz = 0;

        for (int b = 0; b <= N; ++b) {
            int[] split = splitEvenOddBits(b);
            int U = split[0];
            int V = split[1];

            if (V == 0) {
                if (bVZeroSz >= bVZero.length)
                    bVZero = Arrays.copyOf(bVZero, bVZero.length * 2);
                bVZero[bVZeroSz++] = b;
            }
            if (U == 0) {
                if (bUZeroSz >= bUZero.length)
                    bUZero = Arrays.copyOf(bUZero, bUZero.length * 2);
                bUZero[bUZeroSz++] = b;
            }

            if (b == 0 || U == 0 || V == 0) {
                continue;
            }

            int g = polyGcd(U, V);
            int x = polyDivExact(V, g);
            int y = polyDivExact(U, g);
            bGeneral[bGenSz++] = packRecord(packKey(x, y), b);
        }

        for (int a = 1; a <= N; ++a) {
            int[] split = splitEvenOddBits(a);
            int X = split[0];
            int Y = split[1];

            if (X == 0) {
                if (Y != 0) {
                    if (aXZeroSz >= aXZero.length)
                        aXZero = Arrays.copyOf(aXZero, aXZero.length * 2);
                    aXZero[aXZeroSz++] = a;
                }
                continue;
            }
            if (Y == 0) {
                if (aYZeroSz >= aYZero.length)
                    aYZero = Arrays.copyOf(aYZero, aYZero.length * 2);
                aYZero[aYZeroSz++] = a;
                continue;
            }

            int uy = (Y << 1);
            int d = polyGcd(X, uy);
            int x1 = polyDivExact(X, d);
            int y1 = polyDivExact(uy, d);
            aGeneral[aGenSz++] = packRecord(packKey(x1, y1), a);
        }

        Arrays.sort(aGeneral, 0, aGenSz);
        Arrays.sort(bGeneral, 0, bGenSz);

        long total = (long) N + 1L;

        for (int i = 0; i < aXZeroSz; ++i) {
            total += countGe(bVZero, bVZeroSz, aXZero[i]);
        }
        for (int i = 0; i < aYZeroSz; ++i) {
            total += countGe(bUZero, bUZeroSz, aYZero[i]);
        }

        int i = 0;
        int j = 0;
        while (i < aGenSz) {
            int key = recordKey(aGeneral[i]);
            int iEnd = i;
            while (iEnd < aGenSz && recordKey(aGeneral[iEnd]) == key) {
                ++iEnd;
            }

            while (j < bGenSz && recordKey(bGeneral[j]) < key) {
                int skipKey = recordKey(bGeneral[j]);
                while (j < bGenSz && recordKey(bGeneral[j]) == skipKey) {
                    ++j;
                }
            }

            if (j < bGenSz && recordKey(bGeneral[j]) == key) {
                int jEnd = j;
                while (jEnd < bGenSz && recordKey(bGeneral[jEnd]) == key) {
                    ++jEnd;
                }

                int ptr = j;
                for (int p = i; p < iEnd; ++p) {
                    int aValue = recordValue(aGeneral[p]);
                    while (ptr < jEnd && recordValue(bGeneral[ptr]) < aValue) {
                        ++ptr;
                    }
                    total += (jEnd - ptr);
                }
                j = jEnd;
            }

            i = iEnd;
        }

        return Long.toString(total);
    }

    public static void main(String[] args) {
        if (!solve(10).equals("21")) {
            System.out.println("Validation failed");
            return;
        }
        System.out.println(solve(10000000));
    }
}