流行竞技打字平台 SpeedForces 的创始人 Nike Nirzayanov 最近增加了一项新功能，允许用户创建过去比赛的随机混搭（mashup）。
SpeedForces 上的每场比赛包含 $N$ 道实现题，每道题的难度等级都在 $\{800, 900, 1000, 1100, 1200\}$ 之中。单场比赛中的 $N$ 道题目总是按难度非递减顺序排列，并依次分配从 $1$ 到 $N$ 的题目编号。
Busy Beaver 正在测试这项新功能。他首先指定了 $N$ 场过去的比赛，其中他指定的第 $i$ 场比赛包含 $a_{ij}$ 道难度为 $800 + 100(j - 1)$ 的题目（对于每个 $1 \le j \le 5$），且满足 $\sum_{j=1}^5 a_{ij} = N$。
该功能将选择一个 $1, 2, \dots, N$ 的随机排列 $p_1, p_2, \dots, p_N$，并为 Busy Beaver 生成一场比赛，其中第 $i$ 道题目是他所指定的第 $p_i$ 场比赛中的第 $i$ 道题目。
Busy Beaver 想知道：有多少种这样的排列会产生一场难度呈逆序的比赛（即题目难度呈非递增顺序）？出于某种原因，他只需要答案对 $2$ 取模的结果。
输入格式
每个测试点包含多个测试用例。第一行包含测试用例的数量 $T$ ($1 \le T \le 10^4$)。
接下来是各测试用例的描述。
每个测试用例的第一行包含整数 $N$ ($1 \le N \le 2 \cdot 10^5$)，表示过去比赛的数量及题目数量。
接下来的 $N$ 行，每行包含 $5$ 个整数 $a_{i1}, a_{i2}, a_{i3}, a_{i4}, a_{i5}$（其中 $a_{ij} \ge 0$ 且 $\sum_{j=1}^5 a_{ij} = N$）。
保证所有测试用例的 $N$ 之和不超过 $2 \cdot 10^5$。
输出格式
对于每个测试用例，输出一个整数，表示满足条件的排列数量对 $2$ 取模的结果。
子任务
本题共有五个子任务。令 $\sum N$ 为所有测试用例中 $N$ 的总和。令 $K$ 为满足对于某个 $1 \le i \le N$ 有 $a_{ij} > 0$ 的最大 $j$。
- (10 分): $K \le 2$。
- (20 分): $K \le 3, \sum N \le 500$。
- (20 分): $K \le 3$。
- (25 分): $\sum N \le 500$。
- (25 分): 无附加限制。
样例
输入 1
3 3 1 2 0 0 0 0 3 0 0 0 0 0 3 0 0 4 4 0 0 0 0 1 3 0 0 0 0 3 1 0 0 0 2 2 0 0 1 1 0 0 0 0
输出 1
0 1 1
说明
在第一个测试用例中，$N = 3$ 场过去的比赛包含以下题目难度： 比赛 1: 800, 900, 900。 比赛 2: 900, 900, 900。 * 比赛 3: 1000, 1000, 1000。
共有 2 种排列 $p$ 使得比赛难度呈逆序：$p = [3, 1, 2]$ 和 $p = [3, 2, 1]$。因此，答案为 $2 \pmod 2 = 0$。
在第二个测试用例中，$N = 4$ 场过去的比赛包含以下题目难度： 比赛 1: 800, 800, 800, 800。 比赛 2: 800, 900, 900, 900。 比赛 3: 900, 900, 900, 1000。 比赛 4: 900, 900, 1000, 1000。
共有 3 种排列 $p$ 使得比赛难度呈逆序：$p = [3, 4, 2, 1], p = [4, 2, 3, 1]$ 和 $p = [4, 3, 2, 1]$。因此，答案为 $3 \pmod 2 = 1$。
在第三个测试用例中，唯一的排列 $p = [1]$ 生成了难度呈逆序的比赛，因此答案为 $1 \pmod 2 = 1$。