Potential Cow Locations

Farmer John is testing his new automated drone‐mounted cow locator camera. The camera takes an overhead image of the farm as an \(N \times N\) grid of uppercase letters, each representing one of 26 possible colors. A potential cow location (PCL) is defined as a rectangular sub-grid (with sides parallel to the grid) that satisfies the following properties:

• The rectangle contains exactly two distinct colors.
• When considering only the cells inside the rectangle, one color must form exactly one contiguous region while the other color forms at least two contiguous regions. Two cells belong to the same contiguous region if they are adjacent vertically or horizontally.
• The rectangle is maximal, i.e. it is not contained within any other rectangle which also satisfies the above properties.

For example, consider the sub-grid below:

[ \begin{array}{cccccc} A & A & A & A & A \ A & B & A & B & A \ A & A & A & B & B \ \end{array} ]

This rectangle is a PCL because, when focusing on just its contents, one color (say, A) forms a single contiguous region while the other color (B) forms more than one contiguous region. Your task is to count the number of maximal PCLs in the given grid.

inputFormat

The first line of input contains a single integer \(N\) representing the size of the grid. The following \(N\) lines each contain a string of length \(N\), representing a row of the grid. Each character is an uppercase letter from A to Z.

outputFormat

Output a single integer: the number of maximal potential cow locations (PCLs) in the image.

sample

3
ABA
ABB
AAA

1