← 返回题目列表

Codeforces · 120/E

E. 放骑士!

中文机器翻译题面 查看原题

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