Двое играют в игру "Раздели кучку". Изначально есть кучка из n конфет. Любую из кучек можно разбить на две кучки разного размера. Игрок, который не может сделать ход проигрывает. Сколько способов сделать первый ход у первого игрока, чтобы победить при правильной игре обоих.
В первой строке записано количество партий t (1 ≤ t ≤ 10^4
). В следующих t строках записано описание партий: n (1 ≤ n ≤ 10^4
).
Для каждой партии выведите количество способов сделать первый ход у первого игрока, чтобы победить при правильной игре обоих. Если первый игрок проигрывает выведите 0.