Maximum Contiguous Empty Squares

You are given (T) test cases. In each test case, you have an (N\times N) grid where each cell contains either a 0 or a 1. A value of 0 indicates an empty square and 1 indicates a stone. Your task is to determine the maximum area of a square sub-grid that contains only 0s.

Recall that a square with side length (s) has an area of (s^2). If no square consisting entirely of 0s exists, the answer is 0.

This problem can be effectively solved using dynamic programming by considering the largest square ending at each cell.

inputFormat

The input is read from standard input. The first line contains an integer (T) representing the number of test cases. For each test case, the first line contains an integer (N), the size of the grid. This is followed by (N) lines, each containing (N) space-separated integers (either 0 or 1) describing the grid.

outputFormat

For each test case, output a single integer on a new line representing the maximum area of a contiguous square composed solely of 0s.## sample

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

1
4