拼写错误对

题目描述

有 $N$ 个长度为 $M$ 的、由小写英文字母组成的字符串。第 $i$ 个字符串（$1 \le i \le N$）为 $S_i$。

请求出满足以下条件的整数对 $(i,j)$（$1 \le i < j \le N$）的数量：

• $S_i$ 与 $S_j$ 的汉明距离不超过 $2$。

什么是汉明距离？

两个长度均为 $k$ 的字符串 $A$ 与 $B$ 的汉明距离，是满足 $A$ 的第 $i$ 个字符与 $B$ 的第 $i$ 个字符不同的下标 $i$（$1 \le i \le k$）的数量。例如，abc 与 bac 的汉明距离为 $2$，atcoder 与 contest 的汉明距离为 $7$。

输入格式

输入第一行为两个整数 $N,M$。

接下来 $N$ 行，第 $i$ 行为字符串 $S_i$。

输出格式

输出一行一个整数，表示满足条件的整数对数量。

3 3
abc
abd
bac

2

样例 1 解释

• $S_1=$abc 与 $S_2=$abd 的汉明距离为 $1$；
• $S_1=$abc 与 $S_3=$bac 的汉明距离为 $2$；
• $S_2=$abd 与 $S_3=$bac 的汉明距离为 $3$。

因此满足条件的是 $(1,2)$ 与 $(1,3)$ 两对，输出 $2$。

9 5
aaaaa
aaaaa
aaaab
aaaba
aaabb
aabaa
aabab
aabba
aabbb

31

样例 2 解释

同一个字符串可以出现多次。

数据范围

对于所有测试数据，保证：

• $2 \le N \le 2 \times 10^5$；
• $2 \le M \le 6$；
• $N,M$ 是整数；
• $S_i$ 是长度为 $M$ 的、由小写英文字母组成的字符串。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。