Рассмотрим следующую игру. Имеется кучка из N ≥ 2 камней. За один ход можно убрать из неё любое число камней, не превышающее половины размера кучи.

Два игрока совершают ходы поочерёдно. Выигрывает тот, кто сделал последний ход (при этом в куче останется один камень).

Требуется определить, сколько существует различных значений N в интервале от 2 до K, при которых игрок, делающий первый ход, гарантированно проиграет (при условии, что второй игрок всегда ходит наилучшим образом). Например, при K=4 ответом будет 1, поскольку первый игрок гарантированно проиграет только в одном случае − когда в куче три камня.

Формат ответа.

Запишите в результирующий текстовый файл ровно пять чисел − ответы при K, равном:

·        10

·        100

·        1000

·        10⁶

·        10⁹

Числа отделяйте друг от друга пробелом или переводом строки. Если вы не знаете все правильные ответы, то вместо недостающих напишите число 0.

Пример файла с ответами.

100 200 300 400 500

Примечание: в этом примере все ответы неверные

Система оценивания.

Каждый верный ответ оценивается в два балла.