给你 $$$n$$$ 个长度相等的单词 $$$m$$$,由小写拉丁字母组成。第 $$$i$$$ 个单词表示为 $$$s_i$$$。
在一次操作中,您可以选择任何单个单词中的任何位置,并将该位置的字母更改为按字母顺序排列的上一个或下一个字母。例如:
- 您可以将“e”更改为“d”或“f”;
- 'a' 只能更改为 'b';
- 'z' 只能更改为 'y'。
两个单词之间的差异是使它们相等所需的最小移动次数。例如,“最佳”和“成本”之间的差异为 $$$1 + 10 + 0 + 0 = 11$$$。
求 $$$s_i$$$ 和 $$$s_j$$$ 的最小差值,使得 $$$(i < j)$$$。换句话说,找到所有可能的 $$$n$$$ 单词对的最小差异。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含 $$$2$$$ 整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 50$$$, $$$1 \leq m \leq 8$$$) — 分别是字符串的数量和长度。
接下来是 $$$n$$$ 行,其中第 $$$i$$$ 包含长度为 $$$m$$$ 的单个字符串 $$$s_i$$$,由小写拉丁字母组成。
输出
对于每个测试用例,打印一个整数 - 给定字符串的所有可能对的最小差异。
示例
输入 #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
输出 #1
11 8 35 0 200 4
注意
对于第二个测试用例,可以显示最佳配对是 ("abb","bef"),其差异等于 $$$8$$$,可以通过以下方式获得:在一次移动中将第一个字符串的第一个字符更改为 'b',在 $$$3$$$ 移动中将第二个字符串的第二个字符更改为 'b',在 $$$3$$$ 移动中将第二个字符串的第三个字符更改为 'b' $$$4$$$ 移动,因此总计 $$$1 + 3 + 4 = 8$$$ 移动。
对于第三个测试用例,只有一对可能的,可以证明使字符串相等所需的最小移动量是 $$$35$$$。
对于第四个测试用例,有一对字符串已经相等,因此答案是 $$$0$$$。