题目描述

$\red{Farmer John }$的奶牛最近收到了一大块大理石，不幸的是，它有许多缺陷。为了描述这些，我们可以用 $\red{N ×}$ $\red{N }$方格 $\red{(5 <= N <= 300) }$来表示大理石块，其中字符"$\red{*}$"表 示不完美，"."表示不完美。代表大理石的完美部分。

奶牛想在这块大理石上雕刻一个数字"$\red{8}$"（奶牛非常喜欢数字"$\red{8}$"，因为它们的四只脚上都有偶蹄，所以它们可以有效地用它们的"脚趾数到 $\red{8}$" "）。但是，奶牛需要您的帮助来确定大理石 中最佳放置的 $\red{8 }$字形。以下是定义有效数字 $\red{8 }$的一些属性：

$\red{* }$八字形由两个矩形组成，一个顶部和一个底部。$\red{* }$顶部和底部的内部至少有一个单元格。$\red{* }$顶部矩形的底部边缘是底部矩形顶部边缘的（不一定是正确的）子集。

$\red{* }$八字形只能从大理石的无瑕区域雕刻而成。

八字形的美学分数等于其两个矩形所包围的面积的乘积。奶牛希望最大化这个分数。

...............
...............
...*******.....
.*....*.......*
.*......*....*.
....*..........
...*...****....
...............
..**.*..*..*...
...*...**.*....
*..*...*.......
...............
.....*..*......
.........*.....
...............

例如，给定这块大理石

最佳放置的八个是：

..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

顶部矩形的面积为 $\red{6\times9=54，}$底部矩形的面积为 $\red{12\times6=72}$。因此，它的审美分数是 $\red{54\times72=3888}$。

输入格式

第 $\red{1 }$行：一个整数 $\red{N，}$表示弹珠的边长。

第 $\red{2..N+1 }$行：每行描述大理石的一行，包含 $\red{N }$个字符，每个字符都是"$\red{*}$"（不完美）或"." （完美的部分）。

第$\red{1}$行：一个整数$\red{n，}$表示大理石的边长。

行$\red{2 N + 1：}$每行描述了一排大理石，并包含$\red{n}$个字符，每个都是"$\red{*}$"（缺陷）或'.' (完整)。

输出格式

第 $\red{1 }$行：任何不使用任何不完美的大理石方块的八字形中的最高审美分数。如果无法获得数字 $\red{8，}$则输出 $\red{-1}$。

样例

输入样例

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

输出样例

3888

提示

顶部的矩形面积$\red{6\times9 = 54，}$和底部矩形面积$\red{12\times6 = 72}$。因此，它的审美评分$\red{54\times72 = 3888}$。

给出一个$\red{n×}$$\red{n}$的区域，其中有一些位置有瑕疵。现在要在没有瑕疵的位置中雕一个$\red{8}$"出来。

"$\red{8}$"字的定义为两个矩形框，框内面积均大于$\red{0，}$且一个矩形框的底边是是另一个矩形框的顶边的子集。

最大化两矩形框内面积的积。