Largest Square Subgrid of 1s

You are given several test cases. In each test case, you are given a grid with n rows and m columns, where each cell contains either '0' or '1'. Your task is to find the side length of the largest square subgrid that contains only '1's.

The solution can be computed using dynamic programming. Define a DP table \(dp\) where \(dp[i][j]\) represents the side length of the largest square that ends at cell \((i, j)\). The recurrence relation is given by:

[ dp[i][j] = \begin{cases} 0 & \text{if } grid[i][j] = '0', \ 1 & \text{if } grid[i][j] = '1' \text{ and } (i = 0 \text{ or } j = 0), \ \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 & \text{if } grid[i][j] = '1' \text{ and } i, j > 0. \end{cases} ]

The answer for each test case is the maximum value found in the DP table.

inputFormat

The first line of input contains an integer \(T\) representing the number of test cases. For each test case:

• The first line contains two integers \(n\) and \(m\) representing the number of rows and columns respectively.
• The next \(n\) lines each contain a string of length \(m\) consisting of the characters '0' and '1' representing the grid.

outputFormat

For each test case, output a single line containing a single integer denoting the side length of the largest square subgrid that is completely filled with '1's.

## sample

3
5 6
101111
111111
111111
111111
011111
4 4
0110
1111
1111
0110
3 4
1111
1111
1111

4
2
3

</p>