409181: GYM103451 A Game

Two players play following game. Initially they have number $$$ n $$$. Players make alternating turns. If the current number written on the board is more than $$$ 0 $$$ during his move the player can divide the current number by $$$2$$$ with rounding down or substract $$$ 1$$$ from the current number, but such a move can be made only when the current number is odd. (that is, $$$ 4 $$$ per move can be turned into $$$ 2 $$$, and $$$ 7 $$$ into $$$ 3 $$$ or $$$ 6 $$$). The game continues until number $$$ 0 $$$ appears on the board. The player who cannot make a move loses (that is, the player who is forced to move when the number $$$ 0 $$$ is written on the board). Determine who wins if both players play optimally – the one who moved first or the one who moved second. You need to answer $$$ t $$$ independent queries. For each of them print $$$ 1 $$$ if for the given $$$ n $$$ the first player wins, and $$$ 0 $$$ otherwise. Print the answers to the queries in the order in which they appear in the input data.

In first line ypu are given number $$$1 \le t \le 10^3$$$ - number of queries. In following $$$t$$$ lines you are given $$$t$$$ numbers, in each line – number $$$1 \le n \le 10^{18}$$$.

For every query output $$$1$$$ if first player wins and $$$0$$$ otherwise.

3
1
2
3

1
0
1