베시는 어디에?

기술에 밝기로 유명한 농부 존은 드론에 장착하는 새 자동 소 탐지 카메라를 시험하고 있다. 이 카메라는 밭을 촬영해서 소의 위치를 자동으로 찾아낸다고 한다. 하지만 카메라에 들어 있는 소 탐지 알고리즘이 그다지 좋지 않아서, 존은 더 나은 알고리즘을 만드는 데 여러분의 도움이 필요하다.

카메라가 위에서 찍은 농장 사진은 $N \times N$ 격자로 주어진다. 각 칸은 A부터 Z까지의 문자 하나이며, 26가지 색 중 하나를 나타낸다. 존은 소가 있을 만한 위치(PCL)를 다음과 같이 정의했다. PCL은 변이 사진의 변과 평행한 직사각형 부분 격자(사진 전체일 수도 있다)이며, 다른 어떤 PCL에도 포함되지 않는다. 즉 PCL의 더 작은 부분 직사각형은 PCL이 될 수 없다. 또한 PCL은 다음 성질을 만족해야 한다. 사진의 나머지 부분은 무시하고 직사각형 안의 내용만 볼 때, 정확히 두 가지 색이 있어야 하며, 한 색은 연결된 영역 하나를 이루고 다른 색은 연결된 영역 두 개 이상을 이뤄야 한다.

예를 들어 내용이 다음과 같은 직사각형은

AAAAA
ABABA
AAABB

PCL이 된다. A는 연결된 영역 하나를 이루고 B는 연결된 영역 여러 개를 이루기 때문이다. 이것은 B색 얼룩이 있는 A색 소로 해석한다.

어떤 영역 안의 한 칸에서 출발해 상하좌우로 인접한 같은 영역의 칸으로 계속 이동해서 영역 전체를 돌아다닐 수 있으면, 그 영역은 "연결되어" 있다고 한다.

카메라가 찍은 사진이 주어질 때, PCL의 개수를 구하라.

첫째 줄에 격자의 크기 $N$이 주어진다. ($1 \leq N \leq 20$) 다음 $N$개의 줄에는 사진이 주어지며, 각 줄은 $N$개의 문자로 이루어져 있다. 각 문자는 A부터 Z까지의 대문자이다.

사진에 있는 PCL의 개수를 출력한다.

예제에서 PCL은 두 개이며, 각각 내용이 다음과 같은 직사각형이다.

ABB
BBB
AAB
ABB

BC
BC
BB
BC