Maximal Square of Ones

Given a binary matrix of size \(n \times n\) where each cell is either 0 or 1, the task is to find the area of the largest square that contains only 1s. Use the recurrence:

\(dp[i][j] = \min( dp[i-1][j],\, dp[i][j-1],\, dp[i-1][j-1] ) + 1\) if the current cell is 1, and 0 otherwise.

The answer for each test case is \(\text{side}^2\), where \(\text{side}\) is the maximum value obtained in the DP table.

You are given \(T\) test cases. For each test case, the first input line contains an integer \(n\) (the dimension of the grid), followed by \(n\) lines, each containing \(n\) space-separated integers (0 or 1). Output the area of the largest square of 1s for each test case on a new line.

inputFormat

The input is read from stdin. The first line contains an integer (T), the number of test cases. For each test case, the first line contains an integer (n) denoting the size of the grid. The following (n) lines each contain (n) space-separated integers (either 0 or 1), representing the grid.

outputFormat

For each test case, output the area of the largest square consisting entirely of 1s on a new line. The output should be written to stdout.## sample

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

4
4
0