Problem Description

Grace and Edsger are constructing a $N \times N$ boolean matrix $A$. The element in the $i$-th row and $j$-th column is represented by $A_{i,j}$. They decide to note down the checksum (defined as bitwise XOR of given list of elements) along each row and column. Checksum of the $i$-th row is represented as $R_i$. Checksum of the $j$-th column is represented as $C_j$.

For example, if $N = 2$, $A = \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}$, then $R = [1 \quad 0]$ and $C = [0 \quad 1]$.

Once they finished the matrix, Edsger stores the matrix in his computer. However, due to a virus, some of the elements in matrix $A$ are replaced with $-1$ in Edsger's computer. Luckily, Edsger still remembers the checksum values. He would like to restore the matrix, and reaches out to Grace for help. After some investigation, it will take $B_{i,j}$ hours for Grace to recover the original value of $A_{i,j}$ from the disk. Given the final matrix $A$, cost matrix $B$, and checksums along each row ($R$) and column ($C$), can you help Grace decide on the minimum total number of hours needed in order to restore the original matrix $A$?

Input Format

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

The first line of each test case contains a single integer $N$.

The next $N$ lines each contain $N$ integers representing the matrix $A$. The $j$-th element on the $i$-th line represents $A_{i,j}$.

The next $N$ lines each contain $N$ integers representing the matrix $B$. The $j$-th element on the $i$-th line represents $B_{i,j}$.

The next line contains $N$ integers representing the checksum of the rows. The $i$-th element represents $R_i$.

The next line contains $N$ integers representing the checksum of the columns. The $j$-th element represents $C_j$.

Output Format

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from $1$) and $y$ is the minimum number of hours to restore matrix $A$.

3
3
1 -1 0
0 1 0
1 1 1
0 1 0
0 0 0
0 0 0
1 1 1
0 0 1
2
-1 -1
-1 -1
1 10
100 1000
1 0
0 1
3
-1 -1 -1
-1 -1 -1
0 0 0
1 1 3
5 1 4
0 0 0
0 0 0
0 0 0

Case #1: 0
Case #2: 1
Case #3: 2

Hint

In Sample Case #$1$, $A_{1,2}$ can be restored using the checksum of either $1$-st row or $2$-nd column. Hence, Grace can restore the matrix without spending any time to recover the data.

In Sample Case #$2$, Grace spends $1$ hour to recover $A_{1,1}$. After that, she can use checksums of $1$-st row and $1$-st column to restore $A_{1,2}$ and $A_{2,1}$ respectively. And then she can use checksum of $2$-nd row to restore $A_{2,2}$. Hence, Grace can restore the matrix by spending $1$ hour.

In Sample Case #$3$, Grace can spend $1$ hour to recover $A_{1,1}$ and another hour to recover $A_{2,2}$. After that, she can use checksum to restore the rest of the matrix. Hence, Grace can restore the matrix by spending $2$ hours in total.

Limits

$1 \le T \le 100$.

$-1 \le A_{i,j} \le 1$, for all $i$, $j$.

$1 \le B_{i,j} \le 1000$, for $i$, $j$ where $A_{i,j} = -1$, otherwise $B_{i,j} = 0$.

$0 \le R_i \le 1$, for all $i$.

$0 \le C_j \le 1$, for all $j$.

It is guaranteed that there exist at least one way to replace $-1$ in $A$ with $0$ or $1$ such that $R$ and $C$ are satisfied.

Test Set $1$

$1 \le N \le 4$.

Test Set $2$

$1 \le N \le 40$.

Test Set $3$

$1 \le N \le 500$.