B. Mashup
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Nike Nirzayanov, the founder of the popular competitive typing platform SpeedForces, has recently added a new feature allowing users to create random mashups of past contests.

A contest on SpeedForces consists of $$$N$$$ implementation problems, each with a difficulty rating among $$$\{800,900,1000,1100,1200\}$$$. The $$$N$$$ problems in a single contest are always arranged in nondecreasing order of difficulty and assigned problem slots from $$$1$$$ to $$$N$$$ in order.

Busy Beaver is testing out the new feature. He first specifies $$$N$$$ past contests, where the $$$i$$$-th contest he specifies has $$$a_{ij}$$$ problems of difficulty $$$800+100(j-1)$$$ for each $$$1 \le j \le 5$$$, where $$$\sum_{j=1}^5 a_{ij} = N$$$.

The feature will select a random permutation $$$p_1,p_2,\dots,p_N$$$ of $$$1,2,\dots,N$$$ and generate for Busy Beaver a contest where the $$$i$$$-th problem is the $$$i$$$-th problem in the $$$p_i$$$-th contest he specified.

Busy Beaver wonders: How many such permutations will result in a contest with reverse difficulty order (i.e., the problem difficulties are in nonincreasing order)? For some reason, he only wants the answer modulo 2.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \leq T \leq 10^4$$$). The description of the test cases follows.

The first line of each test case contains the integer $$$N$$$ ($$$1 \le N \le 2 \cdot 10^5$$$) — the number of past contests and problems.

The next $$$N$$$ lines of each test case each contain $$$5$$$ integers $$$a_{i1},a_{i2},a_{i3},a_{i4},a_{i5}$$$ ($$$a_{ij} \ge 0$$$ and $$$\sum_{j=1}^5 a_{ij} = N$$$).

It is guaranteed that the sum of $$$N$$$ across all test cases is no more than $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer, the number of such permutations modulo $$$2$$$.

Scoring

There are five subtasks for this problem. Let $$$\sum N$$$ be the sum of $$$N$$$ across all test cases. Let $$$K$$$ be the largest $$$j$$$ such that $$$a_{ij} \gt 0$$$ for some $$$1 \le i \le N$$$.

  • ($$$10$$$ points): $$$K \le 2$$$.
  • ($$$20$$$ points): $$$K \le 3$$$, $$$\sum N \le 500$$$.
  • ($$$20$$$ points): $$$K \le 3$$$.
  • ($$$25$$$ points): $$$\sum N \le 500$$$.
  • ($$$25$$$ points): No additional constraints.
Example
Input
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
Output
0
1
1
Note

In the first test case, the $$$N = 3$$$ past contests have the following problem difficulties:

  • Contest $$$1$$$: $$$800, 900, 900$$$.
  • Contest $$$2$$$: $$$900, 900, 900$$$.
  • Contest $$$3$$$: $$$1000, 1000, 1000$$$.
There are $$$2$$$ permutations $$$p$$$ that result in a reverse difficulty order contest: $$$p = [3, 1, 2]$$$ and $$$p = [3, 2, 1]$$$. Therefore, the answer is $$$2 \bmod 2 = 0$$$.

In the second test case, the $$$N = 4$$$ past contests have the following problem difficulties:

  • Contest $$$1$$$: $$$800, 800, 800, 800$$$.
  • Contest $$$2$$$: $$$800, 900, 900, 900$$$.
  • Contest $$$3$$$: $$$900, 900, 900, 1000$$$.
  • Contest $$$4$$$: $$$900, 900, 1000, 1000$$$.
There are $$$3$$$ permutations $$$p$$$ that result in a reverse difficulty order contest: $$$p = [3, 4, 2, 1]$$$, $$$p = [4, 2, 3, 1]$$$, and $$$p = [4, 3, 2, 1]$$$. Therefore, the answer is $$$3 \bmod 2 = 1$$$.

In the third test case, the only permutation $$$p = [1]$$$ generates a reverse difficulty order contest, so the answer is $$$1 \bmod 2 = 1$$$.