Maximize the Largest Connected 'B' Component

Given an n×n grid that is 4-connected, each cell is either A or B. It is guaranteed that every connected component of B's forms a rectangle.

You are allowed to change at most two A cells to B. After doing so, compute the maximum size of a connected B component.

Formally, let \(G\) be an n×n grid where each cell \(g_{ij}\) is either A or B. Every connected component (using 4-directional connectivity) of cells with value B forms a rectangle. You may select at most two cells \((i,j)\) with value A and convert them to B. Let \(C\) denote a connected component of cells labeled B; determine the maximum possible \(|C|\) (i.e. the area/number of cells) over all such possible modifications.

inputFormat

The first line contains an integer \(n\), the size of the grid. The following \(n\) lines each contain a string of length \(n\), consisting only of characters A and B.

outputFormat

Output a single integer which is the maximum size of a connected B component achievable after converting at most two A cells into B.

sample

3
AAA
ABA
AAA

3