Largest Square Submatrix of 1s

You are given several matrices consisting of 0s and 1s. For each matrix, you are to determine the size (that is, the length of the side) of the largest square submatrix composed solely of 1s.

The problem can be solved using dynamic programming. Define a DP table where each cell (i, j) represents the size of the largest square submatrix ending at that cell. If the original matrix at cell (i, j) is 1, then the DP recurrence is given by: $$dp[i][j] = \min(dp[i-1][j],\ dp[i][j-1],\ dp[i-1][j-1]) + 1.$$ Otherwise, if the cell is 0, then the DP value is 0. The answer for the matrix is the maximum value found in the DP table.

This is a classical dynamic programming problem and is often used to illustrate how local decisions (the minimum of three neighbors) can solve a global problem (finding the largest square).

inputFormat

The first line of input contains an integer T, the number of test cases. Each test case begins with two integers M and N separated by a space (the dimensions of the matrix). The next M lines each contain N integers (0 or 1) separated by spaces representing the matrix.

For example:

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

outputFormat

For each test case, output one integer on a new line: the size of the largest square submatrix composed entirely of 1s.

For the sample input above, the output should be:

3
2

## sample

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

3
2

</p>