问题描述

我们有一个由$N$个水平行和$N$个竖直列组成的网格。
用$(i, j)$表示从上到下的第$i$行和从左到右的第$j$列的方块。字符$c_{i,j}$描述了$(i, j)$的颜色。
B表示方块被涂成黑色；W表示方块被涂成白色；?表示方块尚未被涂色。

高桥将通过将每个未涂色的方块涂成黑色或白色来完成这个黑白网格。
令网格的斑马性为具有共享一条边的黑色方块和白色方块的对数。
找到高桥可以实现的网格的最大可能斑马性。

约束条件

• $1 ≤ N ≤ 100$
• $c_{i, j}$是B、W或?。

输入

输入以以下格式从标准输入中给出：

$N$ $c_{1,1} \\dots c_{1,N}$ $\\hspace{20pt}\\vdots$ $c_{N,1} \\dots c_{N,N}$

输出

打印答案。

示例输入 1

2
BB
BW

示例输出 1

2

我们有两对共享一条边的黑色方块和白色方块：$(1, 2), (2, 2)$和$(2, 1), (2, 2)$，所以这个网格的斑马性为$2$。

示例输入 2

3
BBB
BBB
W?W

示例输出 2

4

将$(3, 2)$涂成白色，使得斑马性为$3$，而将它涂成黑色使得斑马性为$4$。

示例输入 3

5
?????
?????
?????
?????
?????

示例输出 3

40