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