Where's Bessie?#10526

Where's Bessie?

1 second
128 megabytes
Hard

Always known for being quite tech-savvy, Farmer John is testing out his new automated, drone-mounted cow-locator camera, which supposedly can take a picture of his field and automatically determine the locations of cows. Unfortunately, the camera does not have a particularly good algorithm for detecting cows, so FJ needs your help developing a better one.

The overhead image of his farm taken by the camera is represented by an n \times n grid of characters, each in the range , representing one of possible colors. Farmer John decides that the best way to define a potential cow location (PCL) is as follows: a PCL is a rectangular sub-grid (possibly the entire image) with sides parallel to the sides of the image that does not contain any other PCL entirely within it. Furthermore, a PCL must satisfy the following property: considering only the contents of the rectangle and ignoring the rest of the image, exactly two colors must be present, with one color forming a single contiguous region and the other forming two or more contiguous regions.

For example, a rectangle with the following contents

AAAAA
ABABA
AAABB

would constitute a PCL, since the 's form a single contiguous region, while the 's form more than one contiguous region. This can be interpreted as a cow of color with spots of color .

A region is considered "contiguous" if every cell in the region can be reached from every other cell in the region by repeatedly moving up, down, left, or right, while staying within the region.

Given the image returned by FJ's camera, please count the number of PCLs.

Input

The first line contains the size of the grid n~(1 \le n \le 20). The next lines describe the image, each consisting of characters.

Output

Print the number of PCLs in the image.

Examples

Example 1

Loading
Loading