Minimum Sprinklers for Garden Matrices

You are given a series of matrices representing garden plots. Each matrix is an m × n grid where a cell value of 1 indicates the presence of a plant and 0 indicates bare soil. To water the plants, sprinklers can be installed along entire rows or columns. Installing a sprinkler along row i will water all plants in that row; similarly, installing one along column j will water all plants in that column.

Your task is to determine the minimum number of sprinklers required such that every plant is watered. Formally, let \(R\) be the number of rows that contain at least one plant and \(C\) be the number of columns that contain at least one plant. The answer for each matrix is given by:

\( \min(R, C) \)

For each given matrix, compute and print the minimum number of sprinklers needed.

inputFormat

The first line contains an integer \(T\) representing the number of matrices.

For each matrix, the first line contains two integers \(m\) and \(n\) indicating the number of rows and columns respectively. The next \(m\) lines each contain \(n\) integers (either 0 or 1) separated by spaces representing the rows of the matrix.

Input is read from standard input.

outputFormat

For each matrix, output one line with a single integer: the minimum number of sprinklers required to water all plants in that matrix. The output should be printed to standard output.

## sample

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

3
2
1
3
2

</p>