eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 1 second
Memory limit 128 MiB

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

Input data

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

Output data

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

Examples

Input example #1
5
1
2
3
4
9
Output example #1
0
0
1
0
2
Source 2012 Sevastopol, III International Summer Programming School