Farmer John is testing a new camera that can "grab the picture" and automatically calculate the position of the cows. Unfortunately, the camera does not have a very good algorithm for finding cows and the FD needs your help.
The picture taken by the camera can be described by a lattice of NxN characters, each in the range A…Z, representing one of 26 possible different colors. The FD considers the following cow recognition algorithm to be the best: PCL (possible placement of a cow) is a rectangle on a lattice (possibly the entire lattice) with sides parallel to the sides of the lattice, which does not contain other PCLs inside and has the following property: exactly two colors must be present inside this rectangle, one forms a continuous region and the other forms two or more continuous regions.
For example, this image
AAAAA
ABABA
AAABB
is PCL because the A characters form a contiguous region, the B characters form more than one contiguous region. The interpretation is a cow with color A and spots with color B.
A region is continuous if you can traverse the entire region by moving from one cell to another neighboring one in the directions up, down, left, right.
Based on the given image of the PD camera, determine the amount of PCL.
INPUT FORMAT:
The first line of input contains N, the size of the grid (1≤N≤20). The next N lines describe the image, each consisting of N characters.
OUTPUT FORMAT:
Amount of PCL in the image.
| Input |
Output |
|
4
ABBC
BBBC
AABB
ABBC
|
2 |