CF1676C.Most Similar Words

You are given $n$ words of equal length $m$, consisting of lowercase Latin alphabet letters. The $i$-th word is denoted $s_i$.

In one move you can choose any position in any single word and change the letter at that position to the previous or next letter in alphabetical order. For example:

• you can change 'e' to 'd' or to 'f';
• 'a' can only be changed to 'b';
• 'z' can only be changed to 'y'.

The difference between two words is the minimum number of moves required to make them equal. For example, the difference between "best" and "cost" is $1 + 10 + 0 + 0 = 11$.

Find the minimum difference of $s_i$ and $s_j$ such that $(i \lt j)$. In other words, find the minimum difference over all possible pairs of the $n$ words.

给你 $n$ 个长度均为 $m$ 的单词，每个单词均由小写拉丁字母组成。第 $i$ 个单词记为 $s_i$。

一次操作中，你可以任选某个单词中的任意一个位置，并将该位置上的字母替换为字母表中其前一个或后一个字母。例如：

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

两个单词之间的差异定义为：使它们相等所需的最少操作次数。例如，“best”与“cost”的差异为 $1 + 10 + 0 + 0 = 11$。

请找出所有满足 $(i \lt j)$ 的单词对 $(s_i, s_j)$ 中的最小差异值。换言之，求这 $n$ 个单词中所有可能单词对的差异的最小值。

The first line of the input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of test cases follows.

The first line of each test case contains $2$ integers $n$ and $m$ ($2 \leq n \leq 50$, $1 \leq m \leq 8$) — the number of strings and their length respectively.

Then follows $n$ lines, the $i$-th of which containing a single string $s_i$ of length $m$, consisting of lowercase Latin letters.

输入的第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 50$，$1 \leq m \leq 8$），分别表示字符串的数量及其长度。

接下来是 $n$ 行，其中第 $i$ 行包含一个长度为 $m$ 的字符串 $s_i$，由小写拉丁字母组成。

For each test case, print a single integer — the minimum difference over all possible pairs of the given strings.

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

For the second test case, one can show that the best pair is ("abb","bef"), which has difference equal to $8$, which can be obtained in the following way: change the first character of the first string to 'b' in one move, change the second character of the second string to 'b' in $3$ moves and change the third character of the second string to 'b' in $4$ moves, thus making in total $1 + 3 + 4 = 8$ moves.

For the third test case, there is only one possible pair and it can be shown that the minimum amount of moves necessary to make the strings equal is $35$.

For the fourth test case, there is a pair of strings which is already equal, so the answer is $0$.

对于第二个测试用例，可以证明最优的字符串对是 ("abb","bef")，其差异值为 $8$，可通过以下方式实现：将第一个字符串的第一个字符修改为 'b'，耗时 $1$ 步；将第二个字符串的第二个字符修改为 'b'，耗时 $3$ 步；将第二个字符串的第三个字符修改为 'b'，耗时 $4$ 步；总共耗时 $1 + 3 + 4 = 8$ 步。

对于第三个测试用例，仅存在唯一可能的字符串对，且可以证明使其相等所需的最少操作步数为 $35$。

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