CF120E.Put Knight!

Petya and Gena play a very interesting game "Put a Knight!" on a chessboard n × n in size. In this game they take turns to put chess pieces called "knights" on the board so that no two knights could threat each other. A knight located in square (r, c) can threat squares (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) and (r + 2, c - 1) (some of the squares may be located outside the chessboard). The player who can't put a new knight during his move loses. Determine which player wins considering that both players play optimally well and Petya starts.

佩佳和杰纳在一块 $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)$（其中某些格子可能位于棋盘之外）。无法在自己的回合放置新骑士的玩家判负。假设双方均以最优策略进行游戏，且佩佳先行，请判断哪位玩家获胜。

The first line contains integer T (1 ≤ T ≤ 100) — the number of boards, for which you should determine the winning player. Next T lines contain T integers n__i (1 ≤ n__i ≤ 10000) — the sizes of the chessboards.

第一行包含一个整数 $T$（$1 \leq T \leq 100$）—— 表示需要判断获胜玩家的棋盘数量。接下来的 $T$ 行每行包含一个整数 $n_i$（$1 \leq n_i \leq 10000$）—— 表示第 $i$ 个棋盘的尺寸。

For each n__i × n__i board print on a single line "0" if Petya wins considering both players play optimally well. Otherwise, print "1".

对于每个 $n_i \times n_i$ 棋盘，如果双方都以最优策略进行游戏时 Petya 获胜，则在单独一行输出 “0”；否则输出 “1”。