Find the number of components in the given undirected graph.

Input

The input begins with the number t of test cases in a single line (t<=50). Each test case begins with the number n of the order of the adjacency matrix of the undirected graph (n<=100) followed by the adjacency matrix. An adjacency matrix is represented in n lines having n integers (0s or 1s) separated by a space in each line.

Output

For every test case print the number of the components the graph has in a new line.

Example

Input:
7

1
1

2
0 0
0 0

2
0 1
1 0

2
1 1
1 1

3
0 0 0
0 0 0
0 0 0

3
1 1 1
1 0 0
1 0 0

3
0 1 0
1 0 0
0 0 0

Output:
1
2
1
1
3
1
2