PESADA07 - Number of components in an undirected graph

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

Added by:Prof. Channa Bankapur
Date:2015-02-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.