kb = 'qwertyuiop asdfghjkl zxcvbnm'.split(' ')
cs = {}
for y, l in enumerate(kb):
    for x, c in enumerate(l):
        cs[y, x] = c

ds = {}

def d((x1, y1), (x2, y2)):
    return abs(x2 - x1) + abs(y2 - y1)

def dw(w1, w2):
    return sum(ds[c1, c2] for c1, c2 in zip(w1, w2))

for p1, c1 in cs.iteritems():
    for p2, c2 in cs.iteritems():
        ds[c1, c2] = d(p1, p2)

I = input
S = raw_input
L = lambda: raw_input().split(' ')

for _ in xrange(I()):
    w, n = L()
    ws = [ S() for __ in xrange(int(n)) ]
    ss = [ (w1, dw(w, w1)) for w1 in ws ]
    for w, d in sorted(ss, key=lambda(w, d): (d, w)):
        print("{} {}".format(w, d))