Optimal Figure Eight Carving

Farmer John's cows have received a large piece of marble that is marred by imperfections. The marble is represented by an N x N grid (5 ≤ N ≤ 300) where a * indicates an imperfection and a . indicates a flawless region.

The cows wish to carve a figure eight from the flawless regions. A valid figure eight is defined by two rectangles (a top and a bottom) with the following properties:

• Each rectangle must have an interior consisting of at least one cell (i.e. the rectangle must be at least 3×3 in size).
• The horizontal projection of the bottom edge of the top rectangle must be a (not necessarily proper) subset of the horizontal projection of the top edge of the bottom rectangle. In other words, if the top rectangle covers columns [c1, c2] then the bottom rectangle must cover an interval [c3, c4] with c3 ≤ c1 and c2 ≤ c4.
• Both rectangles must lie completely within flawless regions (cells with a .).

The aesthetic score of a figure eight is defined as the product of the areas of the interiors of its top and bottom rectangles. For a rectangle from (r1,c1) to (r2,c2) (with r2 - r1 ≥ 2 and c2 - c1 ≥ 2), its interior area is (r2 − r1 − 1) × (c2 − c1 − 1).

Your task is to determine the maximum aesthetic score attainable by any valid figure eight carved from the given marble. If no valid figure eight exists, output -1.

Example:

Input:
15
...............
...............
...*******.....
.*....*.......*
.*......*....*.
....*..........
...*...****....
...............
..**.*..*..*...
...*...**.*....
*..*...*.......
...............
.....*..*......
.........*.....
...............
Optimal carving (with 8 replacing the carved region):
..88888888888..
..8.........8..
..8*******..8..
.8........8.*
.8........8*.
..8........8..
..8....8..
.88888888888888
.8**.......8
.8....**....8
8..........8
.8............8
.8..........8
.8.......*....8
.88888888888888
The top rectangle has an interior area of 54 and the bottom rectangle has an interior area of 72, so the score is 54 × 72 = 3888.

inputFormat

The first line contains a single integer N (5 ≤ N ≤ 300). Following this are N lines each containing a string of length N made up of the characters . and * representing flawless and imperfect sections of the marble respectively.

outputFormat

Output a single integer — the maximum aesthetic score obtainable by carving a valid figure eight from the flawless regions of the marble. If no valid figure eight exists, output -1.

sample

15
...............
...............
...*******.....
.*....*.......*
.*......*....*.
....*..........
...*...****....
...............
..**.*..*..*...
...*...**.*....
*..*...*.......
...............
.....*..*......
.........*.....
...............

3888