Largest Square Sub-matrix of 1's

You are given a binary matrix (containing only 0's and 1's). Your task is to compute the size of the largest square sub-matrix that consists entirely of 1's. In other words, find the maximum integer ( k ) such that the matrix contains at least one ( k \times k ) sub-matrix with all entries equal to 1.

For example, consider the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

The largest square sub-matrix of 1's has a side length of 2.

Solve the problem by reading multiple test cases from standard input and print the answer for each test case on a new line.

inputFormat

The first line of the input contains an integer ( T ) representing the number of test cases. For each test case, the first line contains two space-separated integers ( M ) and ( N ), denoting the number of rows and columns of the matrix, respectively. This is followed by ( M ) lines, each containing ( N ) space-separated integers (0 or 1) representing the matrix.

outputFormat

For each test case, output a single line containing the side length of the largest square sub-matrix that contains only 1's.## sample

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

2
2