e-olymp
Competitions

ADA Classes - November 8

Square

Jian-Jia has a piece of metal material and he wants to cut a square out of it. The material consists of n by n unit grids and Jian-Jia can only cut the material along grid boundary. Each grid is either usable or defective, and Jian-Jia wants to cut the largest possible square from the material without any defective grids. After determining the maximum size of the square, Jian-Jia also wants to know how many ways he can cut the largest square from this material. Finally Jian-Jia will report the product of the maximum size and the number of possible ways.

Consider the 6 by 6 material in the following figure. The black grids are defective. The largest square Jian-Jia can cut from the material is 3 by 3, and there are two ways to cut it - the red square and the green square. Jian-Jan will report the product of 3 and 2, which is 6.

prb7757.gif

Your task is to find the size of largest squares in the material, count the number of ways to cut them, and report the product of the size and the number.

Input

First line contains the size of the material n (1n1000). Each of the next n lines contains n integers. A 1 means the grid is useful and a 0 means the grid is defective.

Output

Print one integer – the product of the size of largest square in the material, and the number of possible locations in the material.

Time limit 1 second
Memory limit 122.17 MiB
Input example #1
6
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
Output example #1
18
Input example #2
6
0 1 1 1 1 0
1 0 1 1 1 1
0 1 1 1 1 1
1 1 0 1 1 1
1 1 1 1 0 1
1 1 0 1 1 1
Output example #2
6
Source 2014 IOI, Practice Day 0