Petya 和 Gena 玩了一个非常有趣的游戏“放一个骑士!”在大小为 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, c - 1)、(r + 2, c + 1) 和 (r + 2, c - 1)(某些方格可能是位于棋盘之外)。在移动过程中无法放置新马的玩家失败。考虑到两名球员都发挥最佳且佩蒂亚首发,确定哪名球员获胜。
输入
第一行包含整数 T (1 ≤ T ≤ 100) — 棋盘数,您应根据棋盘数确定获胜玩家。接下来的 T 行包含 T 个整数 ni (1 ≤ ni ≤ 10000) — 棋盘的大小。
输出
对于每个 ni × ni 棋盘,如果考虑到两名玩家都发挥最佳表现,Petya 获胜,则在单行上打印“0”。否则,打印“1”。
示例
输入 #1
2 2 1
输出 #1
1 0