Tianjin University Online Judge
Contests Virtual Contests Problems Submit Runs Status Rank List Forum

3494.   Happy to GF
Time Limit: 3.0 Seconds   Memory Limit: 65536K
Total Runs: 242   Accepted Runs: 97

MIKE is together with his girlfriend more than a year. And his girlfriend has a lot of problems. But Mike finds some regulars can make her pleased after concluding a number of key words. Now mike has something to tell her which has many ways to say. It is now want you to figure out how many kinds of words match the key words.

A pattern consists of exactly L tokens. Each token is either a single lowercase letter (Mike is very sure that this is the letter) or a group of unique lowercase letters surrounded by parenthesis ( and ). For example: (ab)d(dc) means the first letter is either a or b, the second letter is definitely d and the last letter is either d or c. Therefore, the pattern (ab)d(dc) can stand for either one of these 4 possibilities: add, adc, bdd, bdc.


The first line of input contains 3 integers, L (0 < L <= 15), D (0 < D <= 5000) and N (0 < N < 500) separated by a space. D lines follow, each containing one word of length L. These are the words that are known to exist in Mike's words. N test cases then follow, each on its own line and each consisting of a pattern as described above. You may assume that all known words provided are unique.


For each test case, output

Case #X: K

where X is the test case number, starting from 1, and K indicates how many words in the key words match the pattern.

Sample Input

3 5 4

Sample Output

Case #1: 2
Case #2: 1
Case #3: 3
Case #4: 0

Source: TJRAC Team Selection 2010 (1)
Submit   List    Runs   Forum   Statistics

Tianjin University Online Judge v1.3.0
Maintance:Fxz. Developer: SuperHacker, G.D.Retop, Fxz