题目描述

给你 $n$ 个长度相等的单词，由小写英文字母组成。第 $i$ 个单词表示为 $s_i$。

每一步操作，您可以选择任何单词中的任何位置，并按英文字母的顺序将该位置的字母更改为其前一个或后一个字母。例如：

您可以将 e 更改为 d 或 f；

a 只能更改为 b；

z 只能更改为 y。

两个单词之间的差异是使它们相等所需的最小移动次数。例如， best 和 cost 之间的差异是 $1+10+0+0=11$。

求 $s_i$ 和 $s_j$ 的最小差异。换句话说，找到所有可能的单词对 $i,j(i<j)$ 的最小差异。

输入格式

输入的第一行包含单个整数 $t(1≤t≤100)$ 表示测试用例的数量。测试用例描述如下。

每个测试用例的第一行包含 $2$ 个整数 $n$ 和 $m(2≤n≤50，1≤m≤8)$，分别为字符串的数量和长度。

然后跟随 $n$ 行，其中第 $i$ 行包含长度为 $m$ 的单个字符串 $s_i$，由小写英文字母组成。

输出格式

对于每个测试用例，输出一个整数，表示给定字符串的所有可能对之间的最小差值。

测试样例

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

样例说明

对于第二个测试用例，我们可以证明最佳对是 (abb,bef)，其差值等于 $8$，可以通过以下方式获得：通过一次操作将第一个字符串的第一个字符更改为 b，通过三次操作将第二个字符串的第二个字符更改成 b ，通过四次操作将第二个串的第三个字符更改到 b。因此总共操作了 $1+3+4=8$ 次。

对于第三个测试用例，只有一个可能的对，可以看出，使字符串相等所需的最小操作量为 $35$。

对于第四个测试用例，有一对字符串已经相等，因此答案为 $0$。