Largest Square Subgrid

You are given a grid consisting of 0's and 1's. Your task is to find the size of the largest square subgrid that is composed entirely of 1's. A square subgrid is a contiguous block of cells forming a square. The problem can be efficiently solved using dynamic programming by maintaining, for each cell, the size of the largest square ending at that cell.

Dynamic Programming Hint: For each cell (i, j) with a value of 1, compute dp[i][j] as follows:

\( dp[i][j] = \min(dp[i-1][j],\, dp[i][j-1],\, dp[i-1][j-1]) + 1 \)

Your solution should process multiple test cases and print the result for each test case on a new line.

inputFormat

The input is read from standard input (stdin). The first line contains an integer T, the number of test cases. Each test case begins with a line containing two space-separated integers N and M, representing the number of rows and columns of the grid, respectively. This is followed by N lines, each containing M space-separated integers (either 0 or 1) that represent the grid.

outputFormat

For each test case, output one integer on a new line representing the size of the largest square subgrid composed entirely of 1's.## sample

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

3