Codeforces Round 790 (Div. 4)

C. 最相似的单词 时间限制: 2 秒 内存限制: 256 MB

你得到 (n) 个长度相同为 (m) 的单词，它们由小写拉丁字母组成。第 (i) 个单词记作 $(s_i)$。

在一次操作中，你可以选择某个单词的任意一个位置，把该位置的字母改成它在字母表中的前一个或后一个字母。例如：

• 'e' 可以变成 'd' 或 'f'；
• 'a' 只能变成 'b'；
• 'z' 只能变成 'y'。

两个单词的差异定义为：将它们变成相同所需的最少操作次数。 例如：单词 "best" 与 "cost" 的差异是 (|'b'-'c'| + |'e'-'o'| + |'s'-'s'| + |'t'-'t'| = 1 + 10 + 0 + 0 = 11)。

你的任务是：在所有满足 (i < j) 的单词对$((s_i, s_j))$ 中，找到最小的差异值。

输入

第一行包含一个整数 $(t) ((1 \leq t \leq 100))$ —— 测试用例的数量。

每个测试用例的第一行包含两个整数 $(n, m) ((2 \leq n \leq 50, 1 \leq m \leq 8))$—— 单词的数量和单词的长度。

接下来有 $(n) 行，每行一个字符串 (s_i)，长度为 (m)，$只包含小写拉丁字母。

输出

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

示例

输入

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")。 差异 = (|'a'-'b'| + |'b'-'e'| + |'b'-'f'| = 1+3+4 = 8)。
• ​第三个测试用例​：只有一个配对，差异是 35。
• ​第四个测试用例​：存在完全相同的单词对，差异 = 0。