Garbled Email

Gagan just got an email from her friend Jorge. The email carries important information, but it was corrupted in transit. All of the spaces are gone, and after the spaces were removed some of the letters were changed into other letters. All Gagan has now is a string $S$ of lowercase characters.

The original email was built out of words from the dictionary described below. The letters were changed after the spaces were removed, and the difference between the indices of any two changed letters is at least $5$. For example, "code jam" could have become "codejam", "dodejbm", "zodejan", or "cidejab", but not "kodezam", because the distance between the index of the "k" change and the index of the "z" change is only $4$.

What is the minimum number of letters that could have been changed?

The dictionary contains $W$ words of at least $1$ and at most $10$ lowercase characters and is given at the start of the input. It is not a dictionary from any natural language, though it does contain some English words. One input carries one dictionary, and every test case in that input uses it. The dictionary is given in lexicographically increasing order and contains no duplicate words.

The first line of the input gives the number of words in the dictionary, $W$. Each of the next $W$ lines contains a string of lowercase characters a to z representing one word of the dictionary. The next line gives the number of test cases, $T$. $T$ test cases follow. Each test case is a single line containing a string $S$ of lowercase characters a to z.

For each test case, print one line containing "Case #x: y", where x is the test case number starting from $1$ and y is the minimum number of letters that could have been changed while $S$ was produced.

• $1 \le W \le 5000$
• Each word of the dictionary has at least $1$ and at most $10$ lowercase characters.
• The dictionary is sorted in lexicographically increasing order.
• The dictionary contains no duplicate words.
• The total number of characters in the dictionary is at most $30000$.
• $1 \le T \le 4$
• $1 \le |S| \le 4000$
• $S$ can be produced by the method described above.

The dictionary is not a natural language dictionary, so an English word is not guaranteed to appear in it. It may hold "operation" and "oo" while it does not hold "cooperation". A stretch that looks like "cooperation" then still has to be split into words the dictionary does hold.