题目描述

题目译自 XXIII Olimpiada Informatyczna — I etap Park wodny

字节水上乐园正角逐最大泳池比赛。乐园地形是一个边长为 $n$ 的正方形，划分为 $n^{2}$ 个小格子，每个格子是边长为 $1$ 的正方形。每个格子要么是小泳池，要么是泳池间的通道。直接相连的小泳池（即边对边相邻的格子）组成更大的泳池。目前，乐园内每个泳池都是矩形。

为了提升获奖机会，乐园管理层决定改造园区。由于时间和预算有限，最多只能将两个通道格子改为小泳池。请你帮助他们设计改造方案，打造包含最多小泳池的泳池。改造后，最大泳池不再必须是矩形。

输入格式

输入第一行是一个正整数 $n$，表示乐园的边长。

接下来的 $n$ 行描述乐园的二维地图，每行包含一个由 $n$ 个字母组成的字符串。字母 A 表示通道格子，字母 B 表示小泳池。假设输入中至少有一个 B。

输出格式

输出一行一个整数，表示可获得的最大泳池包含的小泳池数量。

5
BBBAB
BBBAB
AAAAA
BBABA
BBAAB

14

附加样例

1. $n=10$，地图上仅一个泳池；
2. $n=10$，整个地图全是泳池；
3. $n=1000$，地图呈棋盘格状。

数据范围与提示

详细子任务附加限制及分值如下表所示。