Island Counter

You are given a 2D grid of characters, where each cell is either '1' (representing land) or '0' (representing water). An island is a group of adjacent lands connected horizontally or vertically. Your task is to count the number of islands in the grid.

The grid is provided for multiple test cases. For each test case, the first line is an integer n representing the number of rows in the grid. It is followed by n lines, each containing a string of equal length. Use depth-first search (DFS) or breadth-first search (BFS) to explore the grid and count islands.

The islands are counted even if they consist of a single land cell. If the grid is empty (n = 0), the result should be 0.

inputFormat

The input is read from standard input (stdin) and has the following format:

The first line contains an integer T, the number of test cases. For each test case:

• The first line contains an integer n, the number of rows in the grid.
• Each of the next n lines contains a string representing a row of the grid. All rows are of equal length and contain only the characters '1' and '0'.

outputFormat

For each test case, output a single integer on a new line, representing the number of islands in the corresponding grid.## sample

2
4
11110
11010
11000
00000
4
11000
11000
00100
00011

1
3