Сенсорная клавиатура
В современном мире люди предпочитают сенсорные экраны аппаратным клавиатурам. Часто они случайно нажимают на неправильные буквы из-за маленького размера клавиш и ограниченного пространства экрана.
Обычно после ввода слова запускается проверка орфографии, предлагающая варианты для исправления. Ваша задача — упорядочить этот список так, чтобы наиболее вероятные слова оказались в начале.
Типичная сенсорная клавиатура выглядит следующим образом:
qwertyuiop
asdfghjkl
zxcvbnm
Вам нужно использовать расстояние между буквами для определения вероятности ввода слова: расстояние — это сумма горизонтального и вертикального расстояний между введенной и предложенной буквой. Например, если вы ввели w, расстояние до e равно 1, а до z — 3.
Введенное слово и список слов из проверки орфографии имеют одинаковую длину. Расстояние между двумя словами — это сумма расстояний между соответствующими буквами. Например, расстояние между ifpv и icpc равно 3.
Входные данные
Первая строка ввода содержит количество тестов t (0 < t < 20). Каждый тест начинается со строки и целого числа l в одной строке. Строка представляет слово, введенное с сенсорной клавиатуры, а l указывает количество слов в списке проверки орфографии (0 < l ≤ 10). Далее следуют l строк, каждая из которых содержит одно слово из списка проверки орфографии. Все слова в одном тесте имеют одинаковую длину, и ни одно из них не превышает 10000 символов (только строчные буквы 'a' - 'z'). Кроме того, каждое слово в списке проверки орфографии встречается ровно один раз в одном тесте.
Выходные данные
Для каждого теста выведите список слов, отсортированных по возрастанию их расстояния. Если два слова имеют одинаковое расстояние, отсортируйте их в алфавитном порядке. Укажите расстояние каждого слова в той же строке.