Touchscreen Keyboard

Nowadays, people do not use hardware keyboards but touchscreens. Usually, they touch on the wrong letters with their chunky fingers because screen space is precious, and the letters are therefore too small.

Usually, a spell checker runs after typing a word and suggests other words to select the correct spelling from. Your job is to order that list so that more likely words are on top.

The typical touchscreen keyboard looks like this:

qwertyuiop
asdfghjkl
zxcvbnm

You should use the distance between the letters when typing a word: the distance is the sum of the horizontal and vertical distances between the typed and the proposed letters. Assume you typed a w, the distance to e is 1, while the distance to z is 3.

The typed word and the words in the list of the spell checker all have the same length. The distance between two words is the sum of the distances of their respective letters. So the distance between ifpv and icpc is 3.

Input Specification

The first line of the input specifies the number of test cases t (0 < t < 20). Each test case starts with a string and an integer l in one line. The string gives the word that was typed using the touchscreen keyboard, while l specifies the number of entries in the spell checker list (0 < l ≤ 10). Then follow l lines, each with one word of the spell checker list. You may safely assume that all words of one test case have the same length, and no word is longer than 10 000 characters (which are only lowercase English letters from 'a' to 'z'). Furthermore, each word appears exactly once in the spell checker list in one test case.

Output Specification

For each test case, print the list of words sorted by their distance from the typed word ascending. If two words have the same distance, sort them alphabetically. Print the distance of each word in the same line (after a space).

Sample Input

1. 2
2. ifpv 3
3. iopc
4. icpc
5. gcpc
6. edc 5
7. wsx
8. edc
9. rfv
10. plm
11. qed

download as text file

Output for Sample Input

1. icpc 3
2. gcpc 7
3. iopc 7
4. edc 0
5. rfv 3
6. wsx 3
7. qed 4
8. plm 17

download as text file