eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Раздели кучку

Раздели кучку

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Двое играют в игру "Раздели кучку". Изначально есть кучка из n конфет. Любую из кучек можно разбить на две кучки разного размера. Игрок, который не может сделать ход проигрывает. Сколько способов сделать первый ход у первого игрока, чтобы победить при правильной игре обоих.

Входные данные

В первой строке записано количество партий t (1t10^4). В следующих t строках записано описание партий: n (1n10^4).

Выходные данные

Для каждой партии выведите количество способов сделать первый ход у первого игрока, чтобы победить при правильной игре обоих. Если первый игрок проигрывает выведите 0.

Пример

Входные данные #1
5
1
2
3
4
9
Выходные данные #1
0
0
1
0
2
Источник 2012 Севастополь, III Международная Летняя школа программирования