Maximum Rectangle of Zeros

Given an n × n square matrix consisting of characters '0' and '1', find the area of the largest rectangle that is composed entirely of '0' characters. This rectangle must be contiguous in the matrix.

The problem can be solved by treating each row as a histogram and then applying the largest rectangle in a histogram algorithm to compute the maximum area for rectangles ending at that row.

Formally, if matrix cell \(a_{ij}\) is either '0' or '1', you need to find the maximum \(\text{area} = width \times height\) such that all cells in the submatrix are '0'.

inputFormat

The first line contains an integer n representing the number of rows and columns.

The next n lines each contain a string of exactly n characters, where each character is either '0' or '1'.

outputFormat

Output a single integer representing the area of the largest rectangle composed entirely of '0's.

sample

4
0010
0010
1111
0010

4