You will be given two Bipartite Graphs, each with N vertices. The vertices in both the graphs are labeled from 1 to N.

You have to find the maximum size of a set S of vertices, such that it forms an Independent Set in the first graph, and the subgraph induced by S in the second graph has a perfect matching.

Input Format

The first line will contain an integer T, denoting the number of test cases that follow.

For each of the test cases, the first line will contain an integer N denoting the number of vertices in the two graphs

The next N lines will contain N integers each, denoting the adjacency matrix $A_1$ of the first graph. The $j^{th}$ value in the $i^{th}$ row will represent the value of $A_1(i, j)$, and it is guaranteed that each value of $A_1$ is either 0 or 1, and $A_1(i, j) = A_1(j, i)$.

The next N lines will again contain N integers each, this time denoting the adjacency matrix $A_2$ of the second graph, in a similar fashion as $A_1$.

It is guaranteed that $A_1(i, i) = 0 \text{ and } A_2(i, i) = 0 \quad \forall 1 \le i \le N$ and both $A_1$ and $A_2$ represent adjacency matrices of a bipartite graph.

Output Format

For every test case, output the maximum size of the set S.

Constraints

$1 \le T \le 3$

$1 \le N \le 35$