Connected Components in a Grid

Given a square grid where each cell is either '1' (land) or '0' (water), your task is to determine the number of distinct connected components of land cells. Two cells are considered connected if they are adjacent horizontally or vertically. Use depth-first search (DFS) (or any other method) to traverse the grid and count these components.

The input consists of several test cases, and each test case contains a square grid. For each test case, output the number of connected components on a separate line.

Note: The grid is guaranteed to be square. For example, a grid of size n × n will have exactly n lines, each containing n characters.

Formally, if we denote the grid by \(G\) where \(G_{ij}\) is either '1' or '0', then a connected component of land is a maximal set of indices \((i,j)\) such that \(G_{ij} = '1'\) and for any two cells in the set, there exists a sequence of adjacent moves (up, down, left, right) connecting them.

Your program should read input from standard input (stdin) and write output to standard output (stdout).

inputFormat

The first line of input contains a single integer \(T\) representing the number of test cases. Each test case begins with an integer \(n\) which denotes the size of the grid (number of rows and columns). The next \(n\) lines each contain a string of length \(n\) consisting of characters '1' and '0'.

Example:

5
3
110
010
001
4
1110
0100
0001
0110
1
0
1
1
2
10
01

outputFormat

For each test case, output a single integer on a new line indicating the number of connected components of land cells.

Example Output:

2
3
0
1
2

## sample

5
3
110
010
001
4
1110
0100
0001
0110
1
0
1
1
2
10
01

2
3
0
1
2

</p>