A-to-Z

A-to-Z is a game often played by children in elementary school to sharpen their spelling and grow their vocabulary. The game comes with a set of words, each printed on a plastic tile. Two players challenge each other by picking two letters (call them $C_1$ and $C_2$) and then trying to connect them with a sequence of one or more words $W_1, W_2, \ldots, W_n$ such that the first word $W_1$ starts with $C_1$ and the last word $W_n$ ends with $C_2$.

Every pair of consecutive words $(W_i, W_{i+1})$ must overlap by at least two letters. Word $X$ overlaps word $Y$ by $k$ letters when the last $k$ letters of $X$ are exactly the same as the first $k$ letters of $Y$. For example, in the figure below, a is connected to s by the two-word sequence against students.

Each sequence is given a penalty equal to the number of letters in the sequence, where overlapping letters are counted only once (equivalently, the width of the sequence when the words are laid out overlapping as far as possible). A smaller penalty is better. In the figure, against students has a penalty of 13, while about outside ideas has a penalty of 11.

Given a dictionary of words, determine the minimum possible penalty of a sequence that connects the two given letters.

The input contains one or more test cases. Each test case gives a dictionary of words and a list of queries (letter pairs) to connect using that dictionary.

The first line of a test case is a positive integer $w$, the number of words in the dictionary. The next $w$ lines each contain one word. Words consist of lowercase letters only, and no word is longer than 64 characters. A dictionary has at most 50000 words.

After the dictionary comes an integer $q$, the number of queries, followed by $q$ lines. Each query line contains two lowercase letters $C_1$ and $C_2$ separated by a space.

The input ends with a line containing a single integer $w = 0$, which is not part of the test cases.

For each query, print one line.

Let $a$ be the test case number (starting at 1) and $b$ be the query number within that test case (also starting at 1).

If there is a sequence connecting the two letters, print a.b p, where $p$ is the minimum possible penalty over all valid sequences in the dictionary. If no sequence connects the two letters, print a.b 0.

Because every non-empty sequence has a penalty of at least 1, an output of 0 unambiguously means that no connecting sequence exists. You only need to report the minimum penalty, not an actual winning sequence.