public class Euler306 {
    static int[] computeGrundy(int n) {
        int[] grundy = new int[n + 1];
        int[] seen = new int[2048];
        for (int i = 0; i < 2048; i++) {
            seen[i] = -1;
        }

        for (int len = 1; len <= n; ++len) {
            for (int left = 0; left <= len - 2 - left; ++left) {
                int value = grundy[left] ^ grundy[len - 2 - left];
                seen[value] = len;
            }
            while (seen[grundy[len]] == len) {
                ++grundy[len];
            }
        }
        return grundy;
    }

    public static String solve() {
        int limit = 1000000;
        int prefix = 100;
        int period = 34;
        int maxPrecompute = Math.max(prefix + period, 1200);
        int[] g = computeGrundy(maxPrecompute);

        int wins = 0;
        for (int len = 1; len <= limit; ++len) {
            int sg;
            if (len <= prefix) {
                sg = g[len];
            } else {
                sg = g[(len - prefix) % period + prefix];
            }
            if (sg != 0) {
                wins++;
            }
        }
        return String.valueOf(wins);
    }

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