Byteland 的 Sponge 大学最近在大学生程序设计竞赛中一直处于领先地位。他们最强的队伍——Byteland Vultures——赢得了该领域宇宙锦标赛的冠军。他们不仅赢得了所有的资格赛，而且每次都在比赛结束前很久（标准时长 5 小时）就解决了所有题目。为了不感到无聊，当其他队伍还在努力解题时，Byteland Vultures 玩起了以下游戏：

第一个玩家拿出一个 $n \times n$ 的方形棋盘，并移除其中的一些格子。第二个玩家必须在棋盘剩余的格子上放置 $n$ 个车，并遵守以下规则：

• 车只能放在未被移除的格子上，
• 每个格子上最多只能放一个车，
• 任意两个车不能互相攻击（每一行和每一列必须恰好有一个车）。

这个版本的游戏对宇宙冠军来说太简单了，所以他们修改了规则。玩家不再放置车，而是要计算在遵守上述规则的情况下，在棋盘上放置 $n$ 个车的方法数。第一个给出正确答案的玩家获胜。可能的配置数量可能非常巨大，例如，在一个没有移除任何格子的棋盘上，车可以有 $n!$ 种放置方式。然而，这对宇宙冠军来说是个问题吗？他们心算就能完成所有计算。

你可能还不是世界冠军，所以你的任务会简单一些。你只需要编写一个程序，判断车放置方案的数量是奇数还是偶数。

任务

编写一个程序，完成以下工作：

• 读取棋盘的描述，
• 判断车放置方案的数量是奇数还是偶数，
• 输出答案。

输入格式

第一行包含一个自然数 $t$ —— 棋盘的数量（$1 \le t \le 10$）。接下来是 $t$ 组数据。每组数据的第一行包含一个自然数 $n$ —— 棋盘的维度（$1 \le n \le 250$）。接下来的 $n$ 行描述了棋盘的每一行。在这些行中，每行包含 $n$ 个来自集合 $\{0, 1\}$ 的数字，并用空格分隔。数字 0 表示该格子已被移除，而 1 表示可以在该格子上放置一个车。

输出格式

你的程序应输出 $t$ 个整数，每个整数占一行。第 $i$ 行应包含数字 0 或 1。如果第 $i$ 个棋盘的车放置方案数量为偶数，则输出 0，否则输出 1。

样例

输入 1

2
3
1 1 1
1 1 0
1 0 1
3
1 0 0
0 1 0
0 0 1

输出 1

1
1

样例输入中第一个棋盘的所有可能车放置方案示意图。