Before the Battle of Kamino the Confederacy of Independent Systems developed the a way to communicate with the far systems. This way is very unique as every word consists of exactly L lowercase letters. Also, there are exactly D words in this.

Jedi order intercept these messages and built a dictionary out of it. Now they have to dechiper it to get the messages the Confederacy of Independent Systems transmitting. Unfortunately, these signals are not intercepted properly and some of the words may be misinterpreted. In order to help them decipher these messages, the Jedi order have asked you to devise an algorithm that will determine the number of possible interpretations for a given pattern.

A pattern consists of exactly L tokens. Each token is either a single lowercase letter (the Jedi are 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.

Input

The first line of input contains 3 integers, L, D and N separated by a space. D lines follow, each containing one word of length L. These are the words that are known to exist in the message. 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.

Output

For each test case, output should be K indicating how many words in the message match the pattern.

Limits

1 ≤ L ≤ 15 1 ≤ D ≤ 5000 1 ≤ N ≤ 500