Largest Square with Coins

You are given an N x N grid where each cell is either 1 (coin) or 0 (empty). Your task is to find the side length of the largest square subgrid that contains only coins (i.e., all 1’s). A typical dynamic programming approach can be used by defining a DP state:

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

if grid[i][j] = 1 (and 0 otherwise). The answer for each test case is the maximum value in the DP table.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains a single integer T denoting the number of test cases.
• For each test case:
• The first line contains an integer N (the size of the grid).
• The next N lines each contain N integers (separated by spaces) representing the grid rows (either 0 or 1).

outputFormat

For each test case, output a single integer on a new line representing the side length of the largest square subgrid that consists entirely of coins. The output is written to standard output (stdout).

## sample

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

2
3

</p>