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

Input

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

Output

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