Problem Description

You are given a 4-connected $n \times n$ grid graph. Each cell is either A or B. It is guaranteed that every connected component of B has a rectangular shape.

Now you may change at most two A cells into B. Find the maximum possible size of a connected component of B.

Input Format

The first line contains a positive integer $n$.

The next $n$ lines each contain $n$ characters describing the grid.

Output Format

Output one integer: the size of the largest connected component of B.

5
BBBAB
BBBAB
AAAAA
BBABA
BBAAB

14

Hint

For $100\%$ of the testdata, $1 \le n \le 10^3$.

Translated by ChatGPT 5