题目描述

有一个 $N \\times N$ 的方格网格，某些方格上有方块。
网格由 $N$ 个字符串 $S_1,S_2,\\dots,S_N$ 描述如下。

• 如果 $S_i$ 的第 $j$ 个字符为 #，表示距离顶部第 $i$ 行、左侧第 $j$ 列方格上有方块。
• 如果 $S_i$ 的第 $j$ 个字符为 .，表示距离顶部第 $i$ 行、左侧第 $j$ 列方格没有方块。

高桥可以按以下步骤进行零次或多次操作。

• 首先，在网格内选择一个整数 $D$，$1 \leq D \leq N$，以及一个 $D \times D$ 的子方块区域。
• 然后，花费 $D$ 个体力值摧毁子方块区域内的所有方块。

找到所需的最小体力值，以消除所有方块。

约束条件

• $N$ 是一个整数
• $1 \leq N \leq 50$
• $S_i$ 由 # 和 . 构成
• $|S_i|=N$

输入

从标准输入读入数据，输入的格式如下：

$N$
$S_1$
$S_2$
$\\vdots$
$S_N$

输出

以整数形式打印答案。

示例输入 1

5
##...
.##..
#.#..
.....
....#

示例输出 1

4

通过选择以下子方块区域，高桥将消耗 $4$ 个体力值，这是最优解。

• 以左上角为起点的 $3 \times 3$ 子方块区域。
• 以左上角为起点的 $1 \times 1$ 子方块区域。

示例输入 2

3
...
...
...

示例输出 2

0

可能没有方块在网格上。

示例输入 3

21
.....................
.....................
...#.#...............
....#.............#..
...#.#...........#.#.
..................#..
.....................
.....................
.....................
..........#.....#....
......#..###.........
........#####..#.....
.......#######.......
.....#..#####........
.......#######.......
......#########......
.......#######..#....
......#########......
..#..###########.....
.........###.........
.........###.........

示例输出 3

19