Word Encoding

In any language, certain combinations of letters never appear, or appear so rarely that they can be treated as nonexistent. For example, no English word contains the three-letter combination buv as a substring.

Given a list of forbidden letter combinations, the set of possible "words" in a language shrinks a great deal. Here a "word" is any string of lowercase letters that does not contain any forbidden combination as a substring.

Order all valid words first by increasing length, and among words of the same length alphabetically, then number them starting from 1.

For example, if the forbidden list contains only q, ab, and aaa, the words are numbered like this:

1.   a
2.   b
...
16.  p
17.  r
...
26.  aa
27.  ac
...
649. zz
650. aac

Given the forbidden list, write a program that outputs the number of a given word, and the word of a given number.

Every word has at most 20 characters, and no number (in the input or the output) exceeds 2,000,000,000. The alphabet is always the lowercase letters a to z.

The first line contains the number of test cases $T$.

Each test case begins with a line containing two integers $N$ and $M$, where $N$ is the number of forbidden combinations ($0 \le N \le 1000$) and $M$ is the number of queries ($1 \le M \le 100$).

The next $N$ lines each contain one forbidden combination of between 1 and 3 lowercase letters.

The following $M$ lines each contain one query: either a positive integer or a lowercase word. A word query never contains any forbidden combination of that test case, and a number query never exceeds the total number of valid words.

For each query print a single line: the number of the given word, or the word of the given number.