Put Knight!

题意翻译

佩蒂娅和吉娜玩了一个叫“放一个骑士”的有趣游戏。有一个$n×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,r-1)$，$(r+2,c+1)$和$(r+2,c-1)$（一些正方形可能位于棋盘之外）。。不能在期盼放置新骑士的玩家将失败。注意，佩蒂娅和吉娜都很聪明。 佩蒂亚先下，请确定哪个人获胜。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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".

输入输出样例

输入样例 #1

2
2
1

输出样例 #1

1
0