当前没有测试数据。

题目描述

有一个大小为 $N \times N$ 的矩阵，矩阵的每个位置的值由大写字母 $A \sim Z$ 组成，每种大写字母代表一个独特的颜色。

请从该矩阵中求出满足如下要求的子矩阵的数量。

• 子矩阵包含 $2$ 种颜色。
• 子矩阵中的两种颜色，一种颜色构成 $1$ 个连通块，另一种颜色，构成 $2$ 个或 $2$ 个以上的连通块。
• 两个符合上述条件的子矩阵不能是完全包含的关系，即如果符合条件的子矩阵 $A$ 被符合条件的另一个子矩阵 $B$ 完全包含，则子矩阵 $A$ 不需要被统计。

同一种颜色构成连通块的要求是：从其中一个点，沿上下左右四方向可以走到的同色的位置，构成一个同色连通块。

例如，假设如下矩阵是某矩阵的子矩阵，则其满足上述条件 $1$ 和条件 $2$。

AAAAA
ABABA
AAABB

输入格式

第 $1$ 行读入整数 $N$。

接下来 $N$ 行，每行读入 $N$ 个大写字母。

输出格式

输出满足题意的双色子矩阵的数量。

样例 #1

输入

4
ABBC
BBBC
AABB
ABBC

输出

2

样例 #2

输入

8
BABABBBB
ABAABABA
BAABAAAB
BBABABAB
BBABABAB
AABABAAC
AABBABAC
AACAAAAC

输出

32

样例说明

样例 1 解释

样例 $1$ 包含 $2$ 个符合条件的子矩阵。

第 $1$ 个子矩阵从 $(1, 1)$ 点开始到 $(4, 3)$ 点结束，子矩阵如下。

ABB
BBB
AAB
ABB

第 $2$ 个子矩阵从 $(1, 3)$ 点开始到 $(4, 4)$ 点结束，子矩阵如下。

BC
BC
BB
BC

请注意，子矩阵不可以是完全包含关系，但可以是部分重叠的关系。

数据范围

对于 $10\%$ 的数据，满足矩阵中只有 $1$ 种大写字母。

对于 $100\%$ 的数据，满足 $1 \le N \le 20$。