cho.sh

Alien Language (Small)

For each pattern of tokens (plain letters or letter groups), count how many of the D dictionary words it can match.

Easy3StringBrute forceImplementationInterviewNo attempts yetTime limit5sMemory limit512 MB

Problem

Researchers have decoded an alien language transmitted from a faraway planet. Every word of this language consists of exactly L lowercase letters, and the dictionary holds exactly D words.

Once the dictionary was complete, the researchers found that the aliens had been sending signals to Earth for the past ten years. The distance between the two planets weakens the signals, so some letters may be misread. They need a program that counts how many words a given pattern can stand for.

A pattern consists of exactly L tokens. Each token is either a single lowercase letter or a group of distinct lowercase letters wrapped in ( and ). A single letter means that position is known for certain, and a group means that position holds one of the letters in the group. For example, (ab)d(dc) means the first letter is a or b, the second letter is d, and the third letter is d or c, so it stands for add, adc, bdd, and bdc.

For each pattern, count how many dictionary words match it.

Input

The first line contains three integers L, D, and N separated by spaces. The next D lines each contain one word of length L. These are the words known to exist in the alien language, and they are all distinct. Then N lines follow, each containing one pattern.

Limits

  • 1≤L≤101 \le L \le 10
  • 1≤D≤251 \le D \le 25
  • 1≤N≤101 \le N \le 10

Output

For each pattern, print one line in this format.

Case #X: K

X is the pattern number, starting from 1, and K is the number of dictionary words that match the pattern.