Counting Large Islands

You are given an n × m grid consisting of 0s and 1s, where 1 represents land and 0 represents water. Two cells are considered adjacent if they share a common side (i.e. their Manhattan distance is 1). An island is a maximal set of connected land cells. A large island is defined as an island having at least \( k \) cells, that is, its size \( |island| \geq k \).

Your task is to count the number of large islands in each test case.

Input Format

The first line of the input contains an integer \( T \) representing the number of test cases. For each test case, the first line contains three integers \( n \), \( m \), and \( k \) — the number of rows, columns, and the minimum number of cells for a large island respectively. This is followed by \( n \) lines, each containing \( m \) integers (either 0 or 1), representing the grid.

Output Format

For each test case, output a single integer on a new line: the number of large islands found in the grid.

Note: Two cells are adjacent if they share an edge, i.e. for a cell at position \( (i, j) \), its adjacent cells are \( (i-1,j) \), \( (i+1,j) \), \( (i,j-1) \), and \( (i,j+1) \).

inputFormat

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

T
n m k
row_1 (m space-separated integers)
row_2
...
row_n
... (repeated for each test case)

Where:

• T is the number of test cases.
• For each test case:
• n and m are the dimensions of the grid.
• k is the minimum number of cells for an island to be considered large.
• Each of the next n lines contains m integers (0 or 1) representing a row of the grid.

outputFormat

For each test case, output a single line to stdout containing one integer: the number of large islands in the corresponding grid.

## sample

2
4 5 3
1 1 0 1 0
1 1 0 0 0
0 0 1 1 1
0 1 0 0 0
3 3 2
1 1 0
0 1 1
1 0 0

2
1

</p>