CF120E Put Knight!

Petya 和 Gena 在一个 $n \times n$ 的国际象棋棋盘上玩一个非常有趣的游戏“放骑士！”。在这个游戏中，他们轮流在棋盘上放置名为“骑士”的棋子，使得没有两个骑士能够互相攻击。一个位于 $(r, c)$ 的骑士可以攻击 $(r-1, c+2)$、$(r-1, c-2)$、$(r+1, c+2)$、$(r+1, c-2)$、$(r-2, c+1)$、$(r-2, c-1)$、$(r+2, c+1)$ 和 $(r+2, c-1)$ 这些格子（有些格子可能在棋盘之外）。无法在自己回合放置新骑士的玩家判负。假设双方都采取最优策略，且 Petya 先手，判断哪位玩家会获胜。

第一行包含一个整数 $T$（$1 \leq T \leq 100$），表示需要判断的棋盘数量。接下来的 $T$ 行，每行包含一个整数 $n_i$（$1 \leq n_i \leq 10000$），表示棋盘的大小。

对于每个 $n_i \times n_i$ 的棋盘，如果 Petya 能获胜（双方都采取最优策略），则输出一行“0”；否则输出一行“1”。

由 ChatGPT 4.1 翻译