Maximum Connected Cards After a Flip

You are given an N × N matrix representing cards laid out in a grid. Each card has two sides: one is marked with the letter \(A\) and the other with the letter \(B\). The matrix is filled with the current states of the cards, where each cell is either A or B.

You are allowed to perform the following move exactly once: select any card that is showing B and flip it so that it shows A.

After the flip, consider the connected region of cards that show A. Two cards are considered connected if they are adjacent in one of the four directions (up, down, left, right). Your task is to choose a card (which is originally B) to flip so that the size of the connected region containing that card is maximized, and then output this maximum size.

Example:

For \(N=3\), consider the following matrix:

If you flip the card in the second row, second column (changing it from B to A), the connected region of A cards (using up, down, left, right connections) becomes of size 5. Hence, the answer is 5.

inputFormat

The first line contains an integer (N), the size of the matrix. This is followed by (N) lines, each containing a string of length (N) consisting of characters 'A' and 'B' (without spaces), representing the state of each card.

outputFormat

Output a single integer: the maximum number of connected A cards that can be obtained by flipping exactly one card that is originally B to A.

sample

3
ABB
ABA
BAB

5