Touchscreen Keyboard

These days many people type on touchscreen keyboards. Because the keys sit close together and each key is small, typos happen very often.

To reduce these typos, a spell-check program was written. Despite its name, it only checks for typos.

When the user enters a word, the program takes from its own list the correct words that have the same length as the input and recommends them in order of similarity, showing the most similar word first.

The touchscreen keyboard is laid out like this:

qwertyuiop
asdfghjkl
zxcvbnm

The similarity of two words is measured by their distance on the keyboard. The distance between two words is the sum, over each matching position, of the distance between the two characters there. The distance between two characters is the number of columns apart plus the number of rows apart on the keyboard.

For example, taking w as the reference, its distance to e is 1 and its distance to z is 3. Likewise, the distance between the words icpc and ifpv is 3. The smaller the distance, the more similar the words are.

The first line contains the number of test cases $t$ $(0 < t < 20)$.

The first line of each test case contains the word entered by the user and $l$ $(0 < l \le 10)$, the number of words the program knows. Each of the next $l$ lines contains one of the program's words. Every one of these words has the same length as the user's word, consists only of lowercase letters, and is at most 10,000 characters long. No word appears more than once.

For each test case, sort the recommended words by increasing distance and print each word together with its distance, one per line. If several words have the same distance, order them lexicographically.