C. Самые похожие слова
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны $$$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)$$$. Другими словами, найдите минимальную разницу по всем возможным парам из $$$n$$$ слов.

Входные данные

Первая строка содержит единственное целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следуют описания наборов.

Первая строка каждого набора содержит $$$2$$$ целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 50$$$, $$$1 \leq m \leq 8$$$) — количество слов и их длина соответственно.

Затем следуют $$$n$$$ строк, $$$i$$$-я из которых содержит слово $$$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»), которая имеет разницу, равную $$$8$$$, что можно получить следующим образом: заменить первый символ первой строки на 'b' за один ход, заменить второй символ второй строки на 'b' за $$$3$$$ хода и заменить третий символ второй строки на 'b' за $$$4$$$ хода, что в сумме дает $$$1 + 3 + 4 = 8$$$ ходов.

В третьем наборе существует только одна возможная пара, и можно показать, что минимальное количество ходов, необходимое для того, чтобы строки стали равными, равно $$$35$$$.

В четвертом наборе есть пара строк, которые уже равны, поэтому ответ равен $$$0$$$.