터치스크린 키보드

요즘에는 많은 사람이 터치스크린 키보드를 사용한다. 하지만 터치스크린 키보드는 버튼 사이의 간격이 좁고 버튼 크기도 작아서 오타가 자주 발생한다.

이런 오타를 줄이기 위해 맞춤법 검사 프로그램을 만들었다. 이름은 맞춤법 검사이지만 실제로는 오타만 검사한다.

사용자가 단어를 입력하면, 프로그램은 자신이 가지고 있는 올바른 단어 목록 중에서 입력한 단어와 길이가 같은 단어들을 비슷한 순서대로 추천하며, 가장 비슷한 단어를 가장 먼저 보여준다.

터치스크린 키보드의 배열은 다음과 같다.

qwertyuiop
asdfghjkl
zxcvbnm

두 단어가 비슷한 정도는 키보드 위에서의 거리로 판단한다. 두 단어의 거리는 같은 위치에 있는 문자끼리의 거리를 모두 더한 값이다. 두 문자 사이의 거리는 키보드에서 가로로 떨어진 칸 수와 세로로 떨어진 칸 수를 더한 값이다.

예를 들어 w를 기준으로 하면 e와의 거리는 1이고 z와의 거리는 3이다. 또한 단어 icpc와 ifpv의 거리는 3이다. 거리가 가까울수록 더 비슷한 단어이다.

첫째 줄에 테스트 케이스의 개수 $t$ $(0 < t < 20)$가 주어진다.

각 테스트 케이스의 첫째 줄에는 사용자가 입력한 단어와, 프로그램이 가지고 있는 단어의 개수 $l$ $(0 < l \le 10)$이 주어진다. 이어지는 $l$개의 줄에는 프로그램이 가지고 있는 단어가 한 줄에 하나씩 주어진다. 이 단어들은 모두 사용자가 입력한 단어와 길이가 같고, 알파벳 소문자로만 이루어져 있으며, 길이는 최대 10,000자이다. 또한 같은 단어가 중복되어 등장하지 않는다.

각 테스트 케이스에 대해, 추천하는 단어를 거리가 작은 순서대로 정렬하여 각 단어와 그 거리를 한 줄에 하나씩 출력한다. 거리가 같은 단어가 여러 개라면 사전 순으로 정렬한다.