573. Maximal Square

0

Medium

You have a strong interest in identifying square shapes within a puzzle grid. Given a binary matrix of size n x n, where each element is either 0 or 1, your task is to find the largest square that consists only of 1's and print its area.

Input Format

The first line of input contains an integer n, representing the size of the matrix. The following n lines contain binary strings of length n.

Output Format

Print the area of the largest square.

Example

Input

3
1 0 0
1 1 1
0 1 1

Output

4

Constraints

* 1 <= n <= 300
* Each element in the matrix is either '0' or '1'

Loading...

View Submissions

Console