Maximum Square in a Binary Matrix

You are given a binary matrix (a grid consisting of 0s and 1s). Your task is to find, for each provided test case, the area of the largest square that contains only 1s. Formally, given a matrix \(A\) of size \(M \times N\), you need to identify the maximal side length \(s\) such that there exists a submatrix of size \(s \times s\) where every element is 1. The answer is the area of this square, i.e., \(s^2\).

Input/Output Format: The input is provided through stdin and the output must be printed to stdout. The first line of input contains an integer \(T\), the number of test cases. Each test case begins with two integers \(M\) and \(N\), representing the number of rows and columns of the matrix. This is followed by \(M\) lines, each containing \(N\) space-separated integers (either 0 or 1). For each test case, output a single line containing the area of the largest square of 1s found in the corresponding matrix.

Note: If no square of 1s exists, output 0. Utilize dynamic programming for an efficient solution.

inputFormat

The input begins with an integer \(T\) denoting the number of test cases. For each test case, the first line contains two integers \(M\) and \(N\) indicating the number of rows and columns of the matrix, respectively. The following \(M\) lines each contain \(N\) space-separated integers (either 0 or 1) representing the binary matrix.

outputFormat

For each test case, output one line with a single integer denoting the area of the largest square consisting solely of 1s.

## sample

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

4
1
4

</p>