Garbled Email (Small)

Gagan just got an email from her friend Jorge. The email held important information, but it was corrupted on the way. All of the spaces are gone, and after the spaces were removed some of the letters were changed to other letters. All Gagan has left is a string $S$ of lower-case characters.

The original email was made out of words from the dictionary given 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 index of the "k" change and the index of the "z" change differ by only 4.

Find the minimum number of letters that could have been changed.

The dictionary holds $W$ words, each of at least 1 and at most 10 lower-case characters. It is given once at the start of the input, and every test case in the same input uses it. It is not a dictionary from any natural language, though it does contain some English words. The words are given in lexicographically increasing order and no word appears twice.

The first line has the number of words in the dictionary, $W$. Each of the next $W$ lines has one word made of lower-case characters a-z. The next line has the number of test cases, $T$. Each of the next $T$ lines has one string $S$ made of lower-case characters a-z.

For each test case, print one line in the form 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 to produce $S$.

• $1 \le W \le 50000$
• Each dictionary word has at least 1 and at most 10 lower-case characters.
• The dictionary is sorted in lexicographically increasing order and holds no duplicate word.
• The total number of characters in the dictionary is at most 350000.
• $1 \le T \le 20$
• $1 \le |S| \le 50$
• $S$ can always be produced by the method above.

The index difference is measured on the whole string $S$ and has nothing to do with word boundaries. Changing the last letter of one word and the first letter of the very next word is not allowed, because those two indices differ by 1. A word that is not in the dictionary cannot be used, even if it is an English word.