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 < j)$. In other words, find the minimum difference over all possible pairs of the $n$ words.


-----Input-----

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.


-----Output-----

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


-----Examples-----

Input
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
Output
11
8
35
0
200
4


-----Note-----

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$.

Difficulty: EASY
Tags: String algorithms

Implementation

Greedy algorithms

Complete search

Mathematics
Skill types: Complete search

Greedy algorithms

Starter code:

Solutions:
In = input
for _ in [0] * int(In()):
	n = int(In().split()[0])
	a = [[*map(ord, In())] for _ in [0] * n]
	print(min((sum((abs(x - y) for (x, y) in zip(s, t))) for (i, s) in enumerate(a) for t in a[:i])))


def l1(x, y):
	d = 0
	for i in range(len(x)):
		d += abs(ord(x[i]) - ord(y[i]))
	return d

def ch(x, y, t):
	d = 0
	for i in range(len(x)):
		d += abs(ord(x[i]) - ord(y[i]))
		if d > t:
			return [d, False]
	return [d, True]

def solve(l):
	ans = l1(l[0], l[1])
	n = len(l)
	for i in range(2, n):
		for j in range(i):
			res = ch(l[i], l[j], ans)
			if res[1]:
				ans = res[0]
	return ans
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	l = []
	for _ in range(n):
		l.append(input())
	print(solve(l))


t = int(input().strip())

def diff_1(w, j):
	ans = 0
	for (i, j) in zip(w, j):
		ans += abs(i - j)
	return ans
for _ in range(t):
	(n, m) = map(int, input().split())
	Ws = []
	for _ in range(n):
		Ws.append(list(map(ord, input().strip())))
	cur_min = 10 ** 10
	for i in range(n - 1):
		for j in range(i + 1, n):
			a = diff_1(Ws[i], Ws[j])
			if cur_min > a:
				cur_min = a
	print(cur_min)


for _ in range(int(input())):
	(n, _) = map(int, input().split())
	a = [list(map(ord, input())) for _ in range(n)]
	min_diff = min((sum((abs(u - v) for (u, v) in zip(a[i], a[j]))) for i in range(n) for j in range(i + 1, n)))
	print(min_diff)


m = input
for i in [0] * int(m()):
	n = int(m().split()[0])
	a = [[*map(ord, m())] for j in [0] * n]
	print(min((sum((abs(x - y) for (x, y) in zip(s, t))) for (i, s) in enumerate(a) for t in a[:i])))


I = input
for s in [0] * int(I()):
	n = int(I().split()[0])
	a = [[*map(ord, I())] for k in [0] * n]
	print(min((sum((abs(x - y) for (x, y) in zip(s, t))) for (i, s) in enumerate(a) for t in a[:i])))


d = {'a': 97, 'b': 98, 'c': 99, 'd': 100, 'e': 101, 'f': 102, 'g': 103, 'h': 104, 'i': 105, 'j': 106, 'k': 107, 'l': 108, 'm': 109, 'n': 110, 'o': 111, 'p': 112, 'q': 113, 'r': 114, 's': 115, 't': 116, 'u': 117, 'v': 118, 'w': 119, 'x': 120, 'y': 121, 'z': 122}
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	l = []
	flag = True
	for _ in range(a):
		s = input()
		l.append(s)
		if l.count(s) > 1:
			flag = False
	if flag:
		c = 0
		if len(l) == 2:
			for (i, j) in zip(l[0], l[1]):
				c += abs(d[i] - d[j])
			print(c)
		else:
			m = 1000000
			for i in range(a):
				for j in range(0 + i, a):
					if i != j:
						n = 0
						for (q, w) in zip(l[i], l[j]):
							n += abs(d[q] - d[w])
							if n >= m:
								break
						if n < m:
							m = n
			print(m)
	else:
		print(0)


t = int(input())
for nabor in range(t):
	(n, m) = map(int, input().split())
	arr = tuple((tuple((ord(s) for s in input())) for i in range(n)))
	Max = 200
	for a in range(n - 1):
		for b in range(a + 1, n):
			(Str, str2) = (arr[a], arr[b])
			Sum = 0
			for i in range(m):
				Sum += abs(Str[i] - str2[i])
				if Sum > Max:
					Sum = Max
					break
			Max = Sum
	print(Max)


def dist(s1, s2):
	d = 0
	for (letter1, letter2) in zip(s1, s2):
		d += abs(ord(letter1) - ord(letter2))
	return d

def min_dist(n, m, s):
	ans = 1000000
	for i in range(n - 1):
		for j in range(i + 1, n):
			d = dist(s[i], s[j])
			if d < ans:
				ans = d
	return ans
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	s = []
	for i in range(n):
		s.append(input().strip())
	print(min_dist(n, m, s))


n = int(input())

def ordSum(s, s1):
	res = 0
	for (el, el1) in zip(s, s1):
		res += abs(ord(el) - ord(el1))
	return res

def f(list_, n):
	min = 99999999
	for i in range(n - 1):
		el = list_[i]
		for el1 in list_[i + 1:]:
			a = ordSum(el, el1)
			if min > a:
				min = a
	return min
for i in range(n):
	(n, m) = list(map(int, input().split()))
	s = [input() for x in range(n)]
	print(f(s, n))


t = int(input())
for _ in range(0, t):
	nl = list(map(int, input().rstrip().split()))
	n = nl[0]
	m = nl[1]
	brr = []
	for i in range(0, n):
		arr = list(map(ord, input()))
		brr.append(arr)
	minsum = 1000000
	wsum = 0
	for i in range(0, n):
		for j in range(i + 1, n):
			wsum = 0
			for k in range(0, m):
				wsum += abs(brr[i][k] - brr[j][k])
				if wsum > minsum:
					break
			if wsum <= minsum:
				minsum = wsum
	print(minsum)


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	words = []
	min_diff = m * 26
	for _ in range(n):
		word = list(map(ord, input()))
		for another in words:
			diff = sum([abs(x - y) for (x, y) in zip(word, another)])
			min_diff = min(min_diff, diff)
		words.append(word)
	print(min_diff)


def f(symb):
	return ord(symb) - 97
T = int(input())
for t in range(T):
	(n, m) = map(int, input().split())
	a = []
	h_min = m * 30
	for i in range(n):
		a.append(list(map(f, list(input()))))
		for j in range(i):
			h = 0
			for ind in range(m):
				h += abs(a[i][ind] - a[j][ind])
				if h > h_min:
					break
			else:
				h_min = h
	print(h_min)


import math
import itertools
import heapq
from math import floor, ceil

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def isSubsequence(s, t):
	for i in range(0, len(s)):
		try:
			index = t.index(s[i])
		except ValueError:
			return False
		t = t[index + 1:]
	return True

def diff(a, b):
	ans = 0
	for i in range(len(a)):
		ans += abs(a[i] - b[i])
	return ans
for _ in range(int(input())):
	(N, L) = map(int, input().split())
	words = []
	for i in range(N):
		X = list(input())
		words.append(X)
	for x in range(N):
		for i in range(L):
			words[x][i] = ord(words[x][i]) - 97
	s = float('inf')
	for i in range(N - 1):
		for j in range(i + 1, N):
			s = min(s, diff(words[i], words[j]))
	print(s)


def solve(l):
	n = len(l)
	m = len(l[0])
	min_diff = 1000000000000000000000
	for i in range(n):
		for j in range(i + 1, n):
			diff = 0
			for k in range(m):
				diff += abs(l[i][k] - l[j][k])
			if diff < min_diff:
				min_diff = diff
	print(min_diff)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		x = input()
		l.append([ord(i) - ord('a') for i in x])
	solve(l)


import sys

def solve():
	inp = sys.stdin.readline
	(n, m) = map(int, inp().split())
	a = [None] * n
	for i in range(n):
		a[i] = list(map(ord, inp().strip()))
	res = 1000000000
	for j in range(n):
		for i in range(j):
			cost = 0
			for k in range(m):
				cost += abs(a[i][k] - a[j][k])
			res = min(res, cost)
	print(res)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


def solve(arr, N, M):
	rec = []
	for i in range(N):
		rec.append([ord(c) for c in arr[i]])
	ans = float('inf')
	for i in range(N):
		si = rec[i]
		for j in range(i + 1, N):
			sj = rec[j]
			diff = sum([abs(si[k] - sj[k]) for k in range(M)])
			ans = min(ans, diff)
	return ans
T = int(input())
for _ in range(T):
	(N, M) = list(map(int, input().split()))
	arr = []
	for _ in range(N):
		arr.append(str(input()))
	ans = solve(arr, N=N, M=M)
	print(ans)


from itertools import combinations

def calc(tup, m):
	str1 = tup[0]
	str2 = tup[1]
	summ = 0
	for i in range(m):
		summ += abs(ord(str1[i]) - ord(str2[i]))
	return summ

def solve():
	(n, m) = map(int, input().split())
	arr = list()
	for i in range(n):
		arr.append(input())
	comb = combinations(arr, 2)
	diff_list = list()
	for i in comb:
		diff_list.append(calc(i, m))
	out = min(diff_list)
	print(out)
cases = int(input())
for i in range(cases):
	solve()


t = int(input())

def cost(x, y):
	tmp = 0
	for i in range(m):
		tmp += abs(ord(x[i]) - ord(y[i]))
	return tmp

def func(arr):
	ans = 10 ** 5
	for i in range(n):
		for j in range(i + 1, n):
			ans = min(ans, cost(arr[i], arr[j]))
	return ans
for i in range(t):
	(n, m) = map(int, input().split())
	arr = [[i for i in input()] for _ in range(n)]
	print(func(arr))


def r(a, b):
	s = 0
	for i in range(m):
		s += abs(ord(a[i]) - ord(b[i]))
	return s
t = int(input())
for qwer in range(t):
	(n, m) = map(int, input().split())
	sp = []
	for i in range(n):
		s = list(input())
		sp.append(s)
	ma = r(sp[0], sp[1])
	for i in range(n - 1):
		for j in range(i + 1, n):
			f = r(sp[i], sp[j])
			if ma > f:
				ma = f
	print(ma)


import sys
test_cnt = int(sys.stdin.readline().rstrip())

def get_diff(word1, word2):
	total = 0
	for i in range(len(word1)):
		total += abs(ord(word1[i]) - ord(word2[i]))
	return total

def get_min(w_list, min_num=sys.maxsize):
	if len(w_list) == 1:
		return min_num
	word = w_list.pop()
	min_cnt = min([*[get_diff(word, w) for w in w_list], *[min_num]])
	return get_min(w_list, min_cnt)
for _ in range(test_cnt):
	min_cnt = 0
	(n, m) = map(int, sys.stdin.readline().rstrip().split())
	word_list = [sys.stdin.readline().rstrip() for _ in range(n)]
	print(get_min(word_list))


import sys

def razlika(m, string, s):
	iz = 0
	for i in range(m):
		iz = iz + abs(ord(string[i]) - ord(s[i]))
	return iz

def resi(n, m, lista):
	maxx = sys.maxsize
	for i in range(n):
		for j in range(i + 1, n):
			if maxx > razlika(m, lista[i], lista[j]):
				maxx = razlika(m, lista[i], lista[j])
	print(maxx)
	return
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lista = [input() for i in range(n)]
	resi(n, m, lista)


import math

def khoangcach(s, p):
	S = 0
	for i in range(len(s)):
		S = S + abs(ord(s[i]) - ord(p[i]))
	return S

def Solve():
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		g = input()
		a.append(g)
	MIN = 999999999999999
	for i in range(n - 1):
		for j in range(i + 1, n):
			k = khoangcach(a[i], a[j])
			if k < MIN:
				MIN = k
	print(MIN)
q = int(input())
while q > 0:
	Solve()
	q = q - 1


def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())

def exe():
	minimun = 10 ** 20
	alpha = 'abcdefghijklmnopqrstuvwxyz'
	for i in range(n):
		for j in range(i + 1, n):
			count = 0
			(s1, s2) = (lst[i], lst[j])
			for k in range(m):
				count += abs(alpha.index(s1[k]) - alpha.index(s2[k]))
				if count > minimun:
					break
			else:
				minimun = count
	return minimun
for i in range(int(input())):
	(n, m) = ma()
	lst = []
	for i in range(n):
		lst.append(input())
	print(exe())


count = int(input())

def distance(size, a: str, b: str):
	dist = 0
	for i in range(size):
		dist += abs(ord(a[i]) - ord(b[i]))
	return dist

def min_distance(size, words: list):
	min_dist = distance(size, words[0], words[1])
	for i in range(len(words) - 1):
		for j in range(i + 1, len(words)):
			dist = distance(size, words[i], words[j])
			if dist < min_dist:
				min_dist = dist
	return min_dist
for i in range(count):
	(number, size) = map(int, input().split())
	words = []
	for j in range(number):
		words.append(input())
	print(min_distance(size, words))


import sys
d = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5, 'f': 6, 'g': 7, 'h': 8, 'i': 9, 'j': 10, 'k': 11, 'l': 12, 'm': 13, 'n': 14, 'o': 15, 'p': 16, 'q': 17, 'r': 18, 's': 19, 't': 20, 'u': 21, 'v': 22, 'w': 23, 'x': 24, 'y': 25, 'z': 26}

def ck(w1, w2, m):
	if w1 == w2:
		return 0
	res = 0
	for i in range(m):
		res += abs(d[w1[i]] - d[w2[i]])
	return res

def cal(n, m, a):
	ans = 26 * m
	for i in range(n - 1):
		for j in range(i + 1, n):
			ans = min(ans, ck(a[i], a[j], m))
	return ans
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = [0] * n
	for i in range(n):
		l[i] = input()
	print(cal(n, m, l))


import math

def get_int():
	return int(input())

def get_list():
	return list(map(int, input().split()))

def out(ans):
	if ans:
		print('YES')
	else:
		print('NO')

def check(s, r):
	x = 0
	for i in range(len(s)):
		x += abs(s[i] - r[i])
	return x
alphabet = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
for i in range(get_int()):
	words = []
	(n, m) = get_list()
	for i in range(n):
		words.append(list(map(alphabet.index, list(input()))))
	if n == 1:
		print(0)
	else:
		ans = -1
		x = 0
		while x < n:
			y = x + 1
			while y < n:
				q = check(words[x], words[y])
				if ans == -1 or q < ans:
					ans = q
				y += 1
			x += 1
		print(ans)


from sys import stdin, stdout
import collections
import math

def solve(a, b):
	c = 0
	for i in range(len(a)):
		c += abs(ord(a[i]) - ord(b[i]))
	return c

def main():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		l = []
		for i in range(n):
			l.append(input().strip())
		ans = float('inf')
		for i in range(n):
			for j in range(i + 1, n):
				ans = min(ans, solve(l[i], l[j]))
		print(ans)
	return
input = stdin.readline
main()


def dist(w1, w2):
	d = 0
	for (c1, c2) in zip(w1, w2):
		d += abs(ord(c1) - ord(c2))
	return d
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	words = [input() for _ in range(n)]
	mindist = float('inf')
	for i in range(n - 1):
		w1 = words[i]
		for j in range(i + 1, n):
			mindist = min(mindist, dist(w1, words[j]))
	print(mindist)


def count_dist(s1, s2, length):
	dist = 0
	for i in range(length):
		dist += abs(ord(s1[i]) - ord(s2[i]))
	return dist

def solution(content, n, length):
	mini = 26 * length
	for i in range(n):
		for j in range(i + 1, n):
			dist = count_dist(content[i], content[j], length)
			if dist < mini:
				mini = dist
	print(mini)
t = int(input())
for i in range(t):
	(n, length) = [int(i) for i in input().split()]
	content = []
	for _ in range(n):
		content.append(input())
	solution(content, n, length)


def dif(s1, s2, m):
	cont = 0
	for i in range(m):
		x = abs(ord(s1[i]) - ord(s2[i]))
		cont = cont + x
	return cont

def sol():
	(n, m) = map(int, input().split())
	words = [input() for i in range(n)]
	ans = 1000000000
	for i in range(n):
		for j in range(i + 1, n):
			ans = min(ans, dif(words[i], words[j], m))
	print(ans)
for tt in range(int(input())):
	sol()


def solve(s, t):
	ans = 0
	for i in range(len(s)):
		ans += abs(ord(s[i]) - ord(t[i]))
	return ans
try:
	t = int(input())
	while t:
		(n, m) = map(int, input().split())
		l = []
		res = []
		for i in range(n):
			l.append(input())
		for i in range(0, len(l)):
			for j in range(i + 1, len(l)):
				res.append(solve(l[i], l[j]))
		print(min(res))
		t -= 1
except EOFError:
	pass


def difference(w1, w2, w_len):
	res = 0
	for i in range(w_len):
		res += abs(ord(w1[i]) - ord(w2[i]))
	return res
t = int(input())
for _ in range(t):
	(n, m) = [int(v) for v in input().split()]
	w = [input() for _ in range(n)]
	ans = float('inf')
	for i in range(n - 1):
		for j in range(i + 1, n):
			diff = difference(w[i], w[j], m)
			if diff < ans:
				ans = diff
	print(ans)


def diff(a, b):
	diff = 0
	for k in range(m):
		diff += abs(ord(a[k]) - ord(b[k]))
	return diff
for i in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	strings = []
	for j in range(n):
		string = input()
		strings.append(string)
	dic = float('inf')
	for l in range(n - 1):
		for h in range(l + 1, n):
			temp = diff(strings[l], strings[h])
			if temp < dic:
				dic = temp
	print(dic)


def diff_str(s1, s2, b):
	diff = 0
	for i in range(b):
		diff = diff + abs(ord(s1[i]) - ord(s2[i]))
	return diff

def minimum(l, b):
	diff_list = []
	for i in range(len(l)):
		s1 = l[i]
		for j in range(i + 1, len(l)):
			s2 = l[j]
			diff_list.append(diff_str(s1, s2, b))
	return min(diff_list)
n = int(input())
for i in range(n):
	(a, b) = list(map(int, input().split()))
	l = []
	for j in range(a):
		s = input()
		l.append(s)
	print(minimum(l, b))


def get_distance(w1, w2, l):
	distance = 0
	for i in range(l):
		tmp = ord(w1[i]) - ord(w2[i])
		distance = distance + tmp if tmp > 0 else distance - tmp
	return distance
t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().split()))
	words = []
	for i in range(n):
		words.append(input())
	min_dist = 100000
	for i in range(n - 1):
		for j in range(i + 1, n):
			curr_dist = get_distance(words[i], words[j], m)
			if curr_dist < min_dist:
				min_dist = curr_dist
	print(min_dist)


import math

def dif(a, b):
	s = 0
	for (i, j) in zip(a, b):
		s += abs(ord(i) - ord(j))
	return s
for _ in range(int(input())):
	(n, l) = map(int, input().split())
	r = [input() for i in range(n)]
	m = math.inf
	for i in range(n):
		for j in range(i):
			m = min(m, dif(r[i], r[j]))
	print(m)


def getINP():
	(n, m) = map(int, input().split())
	words = [input() for _ in range(n)]
	return MinMove(words, n, m)

def MinMove(word: list, n: int, m: int):
	diffs = []
	for s1 in range(n - 1):
		for s2 in range(s1 + 1, n):
			diffs.append(countDiff(word[s1], word[s2]))
	return min(diffs)

def countDiff(w1, w2):
	cnt = 0
	for i in range(len(w1)):
		cnt += abs(ord(w1[i]) - ord(w2[i]))
	return cnt
t = int(input())
while t:
	print(getINP())
	t -= 1


def dst(s1, s2):
	p = 0
	for i in range(len(s1)):
		p += abs(ord(s1[i]) - ord(s2[i]))
	return p
for _ in range(int(input())):
	rs = 0
	p = 100000
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(input())
		for j in range(i):
			q = dst(a[i], a[j])
			if q < p:
				p = q
	print(p)


def func(s, t, m):
	d = 0
	for i in range(m):
		d += abs(ord(s[i]) - ord(t[i]))
	return d
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(input())
	ans = 1000000
	cur = 0
	for i in range(n):
		for j in range(i + 1, n):
			cur = func(l[i], l[j], m)
			if cur < ans:
				ans = cur
	print(ans)


def num(s1, s2, m):
	res = 0
	for i in range(m):
		res += abs(ord(s1[i]) - ord(s2[i]))
	return res
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(input())
	d = 10 ** 18
	for i in range(n):
		for j in range(i + 1, n):
			temp = num(l[i], l[j], m)
			if temp < d:
				d = temp
	print(d)


def difference(a, b):
	res = 0
	for i in range(len(a)):
		res += abs(ord(a[i]) - ord(b[i]))
	return res
n = int(input())
for _ in range(n):
	res = 1 << 30
	m = input().split()
	m = int(m[0])
	before = []
	for _ in range(m):
		cur = input()
		for i in before:
			res = min(res, difference(i, cur))
		before.append(cur)
	print(res)


def caldiff(a, b, mm):
	tempv = 0
	for l in range(mm):
		tempv = tempv + abs(ord(a[l]) - ord(b[l]))
	return tempv
t = int(input())
for i in range(t):
	nm = str(input()).split(' ')
	n = int(nm[0])
	m = int(nm[1])
	strings = []
	for j in range(n):
		strings.append(str(input()))
	flag = 0
	mindiff = 0
	for j in range(n):
		for k in range(j + 1, n):
			if flag:
				temp = caldiff(strings[j], strings[k], m)
				if temp < mindiff:
					mindiff = temp
			else:
				flag = 1
				mindiff = caldiff(strings[j], strings[k], m)
	print(mindiff)


def finddiff(s1, s2):
	n = len(s1)
	total = 0
	for i in range(n):
		diff = abs(ord(s1[i]) - ord(s2[i]))
		total = total + diff
	return total
t = int(input())
while t > 0:
	lst = [int(x) for x in input().split()]
	no_of_strings = lst[0]
	lst1 = []
	for i in range(no_of_strings):
		k = input()
		lst1.append(k)
	minval = 10000000
	for i in range(len(lst1)):
		for j in range(i + 1, no_of_strings):
			minval = min(minval, finddiff(lst1[i], lst1[j]))
	print(minval)
	t = t - 1


t = int(input())

def word_diff(a, b):
	diff = 0
	for i in range(len(a)):
		diff += abs(ord(a[i]) - ord(b[i]))
	return diff
for i in range(t):
	the_args = [int(c) for c in input().split()]
	(n, m) = (the_args[0], the_args[1])
	words = []
	for j in range(n):
		words.append(input())
	min_diff = 1000000
	for j in range(n - 1):
		for k in range(j + 1, n):
			min_diff = min(min_diff, word_diff(words[j], words[k]))
	print(min_diff)


def go(a, b):
	s = 0
	for j in range(len(a)):
		s += abs(ord(a[j]) - ord(b[j]))
	return s
for i in range(int(input())):
	(a, b) = list(map(int, input().split()))
	c = list((str(input()) for j in range(a)))
	d = 1000000000
	for j in range(a - 1):
		for k in range(j + 1, a):
			d = min(go(c[j], c[k]), d)
	print(d)


def diff(a, b):
	sum = 0
	for i in range(len(a)):
		sum += abs(ord(a[i]) - ord(b[i]))
	return sum
t = int(input())
for i in range(t):
	ls = []
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	for j in range(n):
		s = input()
		ls.append(s)
	min = diff(ls[0], ls[1])
	for k in range(n - 1):
		for l in range(k + 1, n):
			p = diff(ls[k], ls[l])
			if p < min:
				min = p
	print(min)


def solve(w1, w2, ln):
	res = 0
	for i in range(ln):
		res += abs(ord(w1[i]) - ord(w2[i]))
	return res

def choose(arr, ln):
	if len(arr) == 2:
		return solve(arr[0], arr[1], ln)
	diff = 999
	c = 1
	for i in range(len(arr)):
		for j in range(c, len(arr)):
			df = solve(arr[i], arr[j], ln)
			if df <= diff:
				diff = df
		c += 1
	return diff
inpt = int(input())
for x in range(inpt):
	arr = [int(x) for x in input().split(' ')]
	word = []
	for i in range(arr[0]):
		word.append(input())
	print(choose(word, arr[1]))


t = int(input())

def ordFinder(word1, word2):
	output = 0
	for (let1, let2) in zip(word1, word2):
		output += abs(ord(let1) - ord(let2))
	return output
while t > 0:
	(num, length) = list(map(int, input().split()))
	output = []
	while num:
		string = input()
		output.append(string)
		num -= 1
	min_val = 1000000000000000
	for i in range(len(output)):
		for j in range(i + 1, len(output)):
			dff = abs(ordFinder(output[i], output[j]))
			if dff < min_val:
				min_val = dff
	print(min_val)
	t -= 1


def findDiff(w1, w2):
	diff = 0
	for i in range(len(w1)):
		diff += abs(ord(w1[i]) - ord(w2[i]))
	return diff
n = int(input())
for _ in range(n):
	[n, m] = list(map(int, input().split(' ')))
	words = []
	for i in range(n):
		words.append(input())
	r = float('inf')
	for j in range(len(words)):
		for k in range(j + 1, len(words)):
			r = min(r, findDiff(words[j], words[k]))
	print(r)


n = int(input())
T = []
B = []
for i in range(n):
	t = list(map(int, input().split()))
	T += [t]
	A = []
	for i in range(t[0]):
		A += [str(input())]
	B += [A]
for items in B:
	C = []
	for item in items:
		c = []
		for s in item:
			c += [ord(s) - 97]
		C += [c]
	K = []
	for i in range(len(C)):
		for j in range(i + 1, len(C)):
			Ck = 0
			for (ci, cj) in zip(C[i], C[j]):
				Ck += abs(ci - cj)
			K += [Ck]
	print(min(K))


def steps_min(word1: str, word2: str):
	the_sum = 0
	for i in range(len(word1)):
		the_sum += abs(ord(word1[i]) - ord(word2[i]))
	return the_sum
for i in range(int(input())):
	arr = list(map(int, input().split(' ')))
	(n, m) = (arr[0], arr[1])
	del arr
	words = [input() for j in range(n)]
	sum_all = []
	for h in range(len(words)):
		for j in range(h + 1, len(words)):
			sum_all.append(steps_min(words[h], words[j]))
	print(min(sum_all))


from collections import Counter
t = int(input())
result = []
for _ in range(t):
	(n, m) = map(int, input().split())
	array = []
	for i in range(n):
		array.append(input())
	array.sort()

	def solve(array):
		currentMin = float('inf')
		for i in range(len(array)):
			firstString = array[i]
			for x in range(i + 1, len(array)):
				secondString = array[x]
				count = 0
				for (z, firstChar) in enumerate(firstString):
					secondChar = secondString[z]
					count += abs(ord(secondChar) - ord(firstChar))
				currentMin = min(currentMin, count)
		return currentMin
	ans = solve(array)
	print(ans)


def solution():

	def minimum(w1, w2):
		k = 0
		count = 0
		for i in w1:
			count += abs(ord(i) - ord(w2[k]))
			k += 1
		return count
	result = []
	n = int(input())
	for i in range(n):
		(n2, m) = input().split()
		(n2, m) = (int(n2), int(m))
		word_list = []
		for i in range(n2):
			word_list.append(input())
		cost = [[0 for _ in range(n2)] for _ in range(n2)]
		for i in range(n2):
			res = float('inf')
			only_once = True
			res1 = []
			for j in range(i + 1, n2):
				cost[i][j] = minimum(word_list[i], word_list[j])
		for i in range(n2):
			for j in range(i + 1, n2):
				res = min(res, cost[i][j])
		result.append(res)
	for i in result:
		print(i)
solution()


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_string():
	return list(map(str, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

def get_print_int(x):
	sys.stdout.write(str(x) + '\n')

def get_print(x):
	sys.stdout.write(x + '\n')

def get_print_int_same(x):
	sys.stdout.write(str(x) + ' ')

def get_print_same(x):
	sys.stdout.write(x + ' ')
from sys import maxsize

def helper(s1, s2):
	diff = 0
	for i in range(len(s1)):
		diff += abs(ord(s1[i]) - ord(s2[i]))
	return diff

def solve():
	for _ in range(get_int()):
		(n, m) = get_ints()
		data = []
		for i in range(n):
			data.append(get_string())
		ans = maxsize
		for i in range(n):
			for j in range(i + 1, n):
				ans = min(ans, helper(data[i], data[j]))
		get_print_int(ans)
solve()


def f(x, y):
	res = 0
	for i in range(len(x)):
		res += abs(ord(x[i]) - ord(y[i]))
	return res
for t in '@' * int(input()):
	(a, b) = [*map(int, input().split())]
	w = []
	res = []
	for i in '@' * a:
		w.append(input())
	for i in range(len(w)):
		for j in range(i + 1, len(w)):
			res.append(f(w[i], w[j]))
	print(min(res))


def check(s1, s2):
	val = 0
	for i in range(len(s1)):
		val += abs(ord(s1[i]) - ord(s2[i]))
	return val
for _ in range(int(input())):
	(m, n) = map(int, input().split())
	res = float('inf')
	l = []
	for i in range(m):
		l += [input()]
	for i in range(m):
		for j in range(i + 1, m):
			res = min(res, check(l[i], l[j]))
	print(res)


def diff(word1, word2):
	result = 0
	for i in range(len(word1)):
		result += abs(ord(word1[i]) - ord(word2[i]))
	return result

def main():
	(n, m) = map(int, input().split())
	words = [input() for _ in range(n)]
	result = m * (ord('z') - ord('a') + 1)
	for i in range(n):
		for j in range(i + 1, n):
			result = min(diff(words[i], words[j]), result)
	print(result)
t = int(input())
for _ in range(t):
	main()


def dist(a, b):
	return sum((abs(ord(x) - ord(y)) for (x, y) in zip(a, b)))
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	x = [input() for _ in range(n)]
	min_dist = float('inf')
	for i in range(len(x)):
		for j in range(i + 1, len(x)):
			min_dist = min(min_dist, dist(x[i], x[j]))
	print(min_dist)


def sravnivanie(a, c):
	s = 0
	for i in range(m):
		s += abs(ord(a[i]) - ord(c[i]))
	return s
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	b = []
	for g in range(n):
		b.append(input())
	mi = 100000000000001
	for q in range(n - 1):
		for w in range(q + 1, n):
			if sravnivanie(b[q], b[w]) < mi:
				mi = sravnivanie(b[q], b[w])
	print(mi)


t = int(input())

def calc(s, x):
	res = 0
	for i in range(len(s)):
		res += abs(ord(s[i]) - ord(x[i]))
	return res
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		arr.append(input())
	mini = 2 ** 31
	for i in range(n):
		for j in range(i + 1, n):
			mini = min(mini, calc(arr[i], arr[j]))
	print(mini)


p_nums = input()

def word_to_ascii(word):
	return [ord(c) for c in word]

def get_diff(word_a, word_b, length):
	return sum((abs(word_a[i] - word_b[i]) for i in range(length)))
for i in range(int(p_nums)):
	(cnt, length) = [int(t) for t in input().split()]
	words = []
	for j in range(cnt):
		word = input()
		words.append(word_to_ascii(word))
	curr_min = length * 25
	for j in range(cnt):
		for k in range(cnt - j - 1):
			diff = get_diff(words[j], words[j + k + 1], length)
			curr_min = min(diff, curr_min)
	print(curr_min)


w = list('abcdefghijklmnopqrstuvwxyz')
w_dict = {}
for i in range(26):
	w_dict[w[i]] = i + 1

def dist(s1, s2):
	result = 0
	for i in range(len(s1)):
		result += abs(w_dict[s1[i]] - w_dict[s2[i]])
	return result
t = int(input())
for i in range(t):
	(n, s) = list(map(int, input().split()))
	strings = []
	for j in range(n):
		tmp = input()
		strings.append(tmp)
	ans = 9 * 26
	for j in range(n):
		for k in range(j + 1, n):
			tmp = dist(strings[j], strings[k])
			if tmp < ans:
				ans = tmp
	print(ans)


for _ in range(int(input())):

	def diff(a, b):
		diff = 0
		for i in range(len(a)):
			x = a[i]
			y = b[i]
			diff += abs(ord(x) - ord(y))
		return diff
	(x, y) = map(int, input().split())
	list1 = []
	for i in range(x):
		x1 = input()
		list1.append(x1)
	res = float('inf')
	for i in range(0, x):
		for j in range(i + 1, x):
			res = min(res, diff(list1[i], list1[j]))
	print(res)


T = int(input())

def calc_diff(a, b):
	return sum([abs(a[i] - b[i]) for i in range(len(a))])
for tc in range(T):
	(a, b) = map(int, input().split(' '))
	strings = []
	nums = []
	for i in range(a):
		s = input()
		n = []
		for char in s:
			n.append(ord(char) - 96)
		nums.append(n)
	mindiff = calc_diff(nums[0], nums[1])
	for i in range(1, a):
		for j in range(i):
			diff = calc_diff(nums[i], nums[j])
			mindiff = min(diff, mindiff)
	print(mindiff)


def fun(a, b, l):
	s = 0
	for i in range(l):
		s += abs(ord(a[i]) - ord(b[i]))
	return s
t = int(input())
for _ in range(t):
	(n, ll) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(input().strip())
	m = 10 ** 9
	for i in range(n - 1):
		for j in range(i + 1, n):
			m = min(m, fun(l[i], l[j], ll))
	print(m)


def cost(s, t):
	sum = 0
	for i in range(len(s)):
		sum += abs(ord(s[i]) - ord(t[i]))
	return sum
n = int(input())
for i in range(n):
	(num, length) = list(map(int, input().split()))[:2]
	str = []
	for i in range(num):
		str.append(input())
	ans = 1000
	for i in range(len(str) - 1):
		for j in range(i + 1, len(str)):
			ans = min(cost(str[i], str[j]), ans)
	print(ans)


def diff(a, b, l):
	diff = 0
	for i in range(l):
		diff += abs(ord(a[i]) - ord(b[i]))
	return diff
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	res = 10 ** 5
	a = []
	for k in range(n):
		a.append(input())
	for i in range(n - 1):
		for j in range(i + 1, n):
			res = min(res, diff(a[i], a[j], m))
	print(res)


def diff(a, b):
	d = 0
	for i in range(len(a)):
		d += abs(ord(a[i]) - ord(b[i]))
	return d
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	k = []
	for i in range(n):
		k.append(input())
	mini = 10 ** 9 + 7
	for i in range(n):
		for j in range(i + 1, n):
			mini = min(mini, diff(k[i], k[j]))
	print(mini)


from itertools import combinations

def solve():
	(n, m) = tuple(map(int, input().split()))
	strings = []
	values = []
	for i in range(n):
		strings.append(input())
	for (str1, str2) in combinations(strings, 2):
		sum = 0
		for (char1, char2) in zip(str1, str2):
			sum += abs(ord(char1) - ord(char2))
		values.append(sum)
	return min(values)
t = int(input())
for _ in range(t):
	result = solve()
	print(result)


for _ in range(int(input())):
	minimum = 99999
	(n, m) = input().split()
	words = []
	for _ in range(int(n)):
		words.append(input())
	for i in range(len(words)):
		for j in range(i + 1, len(words)):
			diff = sum([abs(ord(c1) - ord(c2)) for (c1, c2) in zip(words[i], words[j])])
			if diff < minimum:
				minimum = diff
	print(minimum)


import sys

def moves(src, target):
	tot = 0
	for i in range(len(src)):
		tot += abs(ord(src[i]) - ord(target[i]))
	return tot

def minmoves(l):
	ans = sys.maxsize
	res = 0
	tot = 0
	for i in range(len(l)):
		for j in range(i + 1, len(l)):
			ans = min(ans, moves(l[i], l[j]))
	print(ans)
t = int(input())
for i in range(t):
	(n, m) = input().split(' ')
	n = int(n)
	m = int(m)
	l = [input() for i in range(n)]
	minmoves(l)


def transform(w1, w2):
	n = len(w1)
	res = 0
	for i in range(n):
		res += abs(ord(w1[i]) - ord(w2[i]))
	return res

def solve():
	(n, m) = map(int, input().split())
	words = [input() for i in range(n)]
	ans = 10000000000000000000
	for i in range(n):
		for j in range(i + 1, n):
			ans = min(ans, transform(words[i], words[j]))
	print(ans)
for i in range(int(input())):
	solve()


def calc_cost(w1, w2, m):
	if w1 == w2:
		return 0
	moves = 0
	for i in range(m):
		moves += abs(ord(w1[i]) - ord(w2[i]))
	return moves
t = int(input())
while t:
	(n, m) = map(int, input().split())
	words = n * [0]
	for i in range(n):
		word = input()
		words[i] = word
	minn = []
	for i in range(n):
		for j in range(i + 1, n):
			minn.append(calc_cost(words[i], words[j], m))
	print(min(minn))
	t -= 1


t = int(input())

def cost(a, b):
	s = 0
	for i in range(len(a)):
		s += abs(ord(a[i]) - ord(b[i]))
	return s

def solve():
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		x = input()
		a.append(x)
	ans = 9999999
	for i in range(n):
		for j in range(i + 1, n):
			ans = min(ans, cost(a[i], a[j]))
	print(ans)
while t:
	t = t - 1
	solve()


u = int(input())

def similarword(w1, w2, x):
	if w1 == w2:
		return 0
	res = 0
	for i in range(x):
		res += abs(ord(w1[i]) - ord(w2[i]))
	return res

def cal(y, x, a):
	ans = 26 * x
	for i in range(y - 1):
		for j in range(i + 1, y):
			ans = min(ans, similarword(a[i], a[j], x))
	return ans
for jj in range(u):
	(y, x) = [int(i) for i in input().split(' ')]
	a = []
	for i in range(y):
		a.append(input())
	print(cal(y, x, a))


def distance(s1, s2, m):
	dist = 0
	for i in range(m):
		dist += abs(ord(s1[i]) - ord(s2[i]))
	return dist
t = int(input())
while t > 0:
	(n, m) = list(map(int, input().split(' ')))
	a = []
	for i in range(n):
		a.append(input())
	result = 1000000000.0
	for i in range(n):
		for j in range(i + 1, n):
			result = min(result, distance(a[i], a[j], m))
	print(result)
	t -= 1


def dif(a, b, m):
	s = 0
	for i in range(m):
		s += abs(ord(a[i]) - ord(b[i]))
	return s
for i in range(int(input())):
	(n, m) = map(int, input().split())
	l = [input() for i in [0] * n]
	x = []
	for i in range(len(l)):
		for j in range(i + 1, len(l)):
			x.append(dif(l[i], l[j], m))
	print(min(x))


def cum(a, b):
	res = 0
	for i in range(0, len(a)):
		res += abs(ord(a[i]) - ord(b[i]))
	return res
for _ in range(0, int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(0, n):
		s = input()
		l.append(s)
	res = m * 26
	for i in range(0, len(l) - 1):
		for j in range(i + 1, len(l)):
			now = cum(l[i], l[j])
			if now < res:
				res = now
	print(res)


def dif(a: str, b: str) -> int:
	return sum((abs(ord(x) - ord(y)) for (x, y) in zip(a, b)))

def solve():
	(n, m) = map(int, input().split())
	s = [input() for _ in range(n)]
	ans = 10 ** 10
	for i in range(n):
		for j in range(i + 1, n):
			ans = min(ans, dif(s[i], s[j]))
	print(ans)
for _ in range(int(input())):
	solve()


def diff_str(str1, str2):
	count = 0
	for i in range(len(str1)):
		count += abs(ord(str1[i]) - ord(str2[i]))
	return count
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	string_list = []
	for _ in range(n):
		string = input()
		string_list.append(string)
	min_num = float('inf')
	for i in range(n):
		for j in range(i + 1, n):
			diff = diff_str(string_list[i], string_list[j])
			if diff < min_num:
				min_num = diff
	print(min_num)


def answer():
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(input())
	a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
	ans = 10 ** 6
	for i in range(n):
		for j in range(i + 1, n):
			s = 0
			for k in range(m):
				mn = abs(ord(l[i][k]) - ord(l[j][k]))
				s += mn
			ans = min(ans, s)
	print(ans)
for _ in range(int(input())):
	answer()


import math

def inp():
	return int(input())

def invr():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s)])

def min_diff_result(ls1, ls2):
	min_diff = 0
	if len(ls1) != len(ls2):
		print('two word does not have the same lenth')
	for k in range(len(ls1)):
		min_diff += abs(ls1[k] - ls2[k])
	return min_diff
T = inp()
for _ in range(T):
	(n_num, len_num) = invr()[:]
	num_ls = []
	min_num = 0
	for i in range(n_num):
		num_ls.append([])
		s = insr()
		for j in range(len_num):
			num_tmp = ord(s[j]) - 96
			num_ls[i].append(num_tmp)
	min_diff = min_diff_result(num_ls[0], num_ls[1])
	for i in range(n_num):
		if min_diff == 0:
			break
		for j in range(n_num):
			if j > i:
				(ls1, ls2) = (num_ls[i], num_ls[j])
				min_diff = min(min_diff, min_diff_result(ls1, ls2))
	print(min_diff)


def help(s1, s2):
	res = 0
	for i in range(len(s1)):
		res += abs(ord(s1[i]) - ord(s2[i]))
	return res
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	l = []
	for i in range(n):
		l.append(input())
	ans = 1000000000000
	for i in range(n):
		for j in range(i + 1, n):
			ans = min(ans, help(l[i], l[j]))
	print(ans)


def strDiff(s1, s2):
	total = 0
	for i in range(len(s1)):
		total += abs(ord(s1[i]) - ord(s2[i]))
	return total
t = int(input())
while t > 0:
	t -= 1
	(n, m) = [int(num) for num in input().split(' ')]
	words = []
	for i in range(n):
		words.append(input())
	minDiff = 100 * 50
	for i in range(n):
		for j in range(i + 1, n):
			minDiff = min(minDiff, strDiff(words[i], words[j]))
	print(minDiff)


t = int(input())

def solve(ar):
	n = len(ar)

	def cst(u, v):
		ans = 0
		for i in range(len(u)):
			ft = abs(ord(u[i]) - ord(v[i]))
			ans += ft
		return ans
	mn = float('inf')
	for i in range(n):
		for j in range(i + 1, n):
			mn = min(mn, cst(ar[i], ar[j]))
	return mn
for _ in range(t):
	lst = []
	(w, l) = list(map(int, input().split()))
	for i in range(w):
		x = input()
		lst.append(x)
	print(solve(lst))


def diff(s1, s2):
	res = 0
	for i in range(len(s1)):
		res = res + abs(ord(s1[i]) - ord(s2[i]))
	return res
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	words = []
	for _ in range(n):
		s = input()
		words.append(s)
	res = diff(words[0], words[1])
	for i in range(n - 1):
		for k in range(i + 1, n):
			if k != i:
				d = diff(words[i], words[k])
				if d < res:
					res = d
	print(res)