Problem I
Graph representation
Tuan has studied a matrix multiplication. Remember that when multiplying two matrices $A = \{ a_{ik}\} $ and $B = \{ b_{kj}\} $ with sizes of $m\times p$ and $p\times n$ respectively, we get matrix $C = \{ c_{ij}\} $ size $m\times n$, where
$c_{ij}=\sum ^{p}_{k=1} a_{ik} b_{kj}.$
After discovering a variety of matrices, Tuan sees that the adjacency matrix of some undirected pseudographs could be represented by the product of two (0,1)-vectors, so one can reduce memory space to represent the graph. For example, the matrix
\[ A = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix} \]can be represented as product of two vectors as follows
\[ \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} \begin{bmatrix} 1 & 1 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix} \]Your task is to write a program to compute the number of connected components of a given undirected pseudograph, that is represented by the product of two (0,1)-vectors.
Input
The input consists of several datasets. The first line of the input contains the number of datasets, which is a positive number and is not greater than 30. The following lines describe the datasets.
Each dataset is described by the following lines:
-
The first line contains the integer number $n$ ($1 \leq n \leq 10^4$) – the number vertices of a given undirected pseudograph.
-
The next two lines, each one contains $n$ numbers (0 or 1), describe two vectors whose product gives an adjacency matrix of the given graph. The data ensures that the product of the two given vectors yields an adjacency matrix of some undirected pseudograph.
Output
For each dataset, write out on one line the number of connected components.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 3 1 1 0 1 1 0 |
2 |
