Alien Language (Large)

A research team decoded an alien language transmitted from a distant planet. Every word of this language is exactly $L$ lowercase letters long, and the dictionary holds exactly $D$ words.

After the dictionary was finished, the team found that the aliens had been sending signals to Earth for the past ten years. The distance between the two planets weakens the signal, so some letters arrive in a state that can be read in more than one way. Count how many dictionary words a given pattern can stand for.

A pattern is exactly $L$ tokens. Each token is either a single lowercase letter or a group of distinct lowercase letters wrapped in the parentheses ( and ). A single-letter token means the letter at that position is fixed, and a group token means the letter at that position is one of the letters inside 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 the four words add, adc, bdd, bdc.

The first line contains the integers $L$, $D$, $N$ separated by spaces. Each of the next $D$ lines contains one word of length $L$. These words are known to exist in the alien language, and they are all different. Each of the following $N$ lines contains one pattern in the format described above.

Limits

• $1 \le L \le 15$
• $1 \le D \le 5000$
• $1 \le N \le 500$

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.