public class Euler878 {

    static long clmul(long x, long y) {
        long r = 0;
        while (y > 0) {
            if ((y & 1L) != 0)
                r ^= x;
            x <<= 1L;
            y >>= 1L;
        }
        return r;
    }

    static long valueF(long a, long b) {
        return clmul(a, a) ^ clmul(clmul(2L, a), b) ^ clmul(b, b);
    }

    static long seedBound(long m) {
        if (m == 0)
            return 1;
        int bits = 0;
        long t = m;
        while (t > 0) {
            ++bits;
            t >>= 1;
        }
        return 1L << ((bits + 2) / 2);
    }

    static long countFast(long n, long m) {
        if (m == 0)
            return 1;

        long bmax = seedBound(m);
        long total = 0;

        for (long b = 0; b < bmax; ++b) {
            for (long a = 0; a <= b; ++a) {
                long k = valueF(a, b);
                if (k > m)
                    continue;

                if (a == 0 && b == 0) {
                    ++total;
                    continue;
                }

                long prev = b ^ (a << 1L);
                if (prev <= a)
                    continue;

                long aa = a;
                long bb = b;
                while (bb >= 0 && bb <= n) {
                    ++total;
                    long nextVal = (bb << 1L) ^ aa;
                    aa = bb;
                    bb = nextVal;
                }
            }
        }

        return total;
    }

    public static String solve() {
        return Long.toString(countFast(100000000000000000L, 1000000L));
    }

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