题目描述

给定 $n$ 个长度相同为 $m$ 的单词，这些单词均由小写拉丁字母组成。第 $i$ 个单词记为 $s_i$。

每次操作，你可以选择任意一个单词中的任意一个位置，将该位置的字母更改为字母表中的前一个或后一个字母。例如：

• 你可以将 'e' 改为 'd' 或 'f'；
• 'a' 只能改为 'b'；
• 'z' 只能改为 'y'。

两个单词之间的差异定义为：将它们变为相同所需的最少操作次数。例如，"best" 和 "cost" 之间的差异为 $1 + 10 + 0 + 0 = 11$。

请你求出所有可能的单词对 $s_i$ 和 $s_j$（其中 $i < j$）中，差异的最小值。

输入格式

输入的第一行为一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行为两个整数 $n$ 和 $m$（$2 \leq n \leq 50$，$1 \leq m \leq 8$），分别表示单词的数量和每个单词的长度。

接下来有 $n$ 行，每行一个长度为 $m$ 的字符串 $s_i$，均由小写拉丁字母组成。

输出格式

对于每个测试用例，输出一个整数，表示所有给定单词对中差异的最小值。

说明/提示

对于第二个测试用例，可以证明最优的单词对是（"abb","bef"），它们的差异为 $8$，具体操作如下：将第一个单词的第一个字符改为 'b'，需要 $1$ 次操作；将第二个单词的第二个字符改为 'b'，需要 $3$ 次操作；将第二个单词的第三个字符改为 'b'，需要 $4$ 次操作，总共 $1 + 3 + 4 = 8$ 次操作。

对于第三个测试用例，只有一组单词对，可以证明将两个单词变为相同所需的最少操作次数为 $35$。

对于第四个测试用例，有一组单词已经完全相同，因此答案为 $0$。

由 ChatGPT 4.1 翻译

样例

6
2 4
best
cost
6 3
abb
zba
bef
cdu
ooo
zzz
2 7
aaabbbc
bbaezfe
3 2
ab
ab
ab
2 8
aaaaaaaa
zzzzzzzz
3 1
a
u
y

11
8
35
0
200
4