经过多年的研究，Google 实验室的科学家们发现了一种来自遥远星球的外星语言。这种外星语言非常独特，每个单词都恰好由 $L$ 个小写字母组成。此外，该语言中恰好有 $D$ 个单词。

在建立了外星语言的完整词典后，下一个突破是发现外星人过去十年来一直在向地球发送信息。不幸的是，由于两个星球之间的距离，这些信号有所减弱，导致一些单词可能会被误读。为了帮助他们破译这些信息，科学家们请你设计一种算法，用于确定给定模式下可能的解释数量。

一个模式恰好由 $L$ 个标记（token）组成。每个标记要么是一个小写字母（科学家非常确定这就是该位置的字母），要么是一组由括号 ( 和 ) 包围的唯一小写字母。例如：(ab)d(dc) 表示第一个字母是 a 或 b，第二个字母确定是 d，最后一个字母是 d 或 c。因此，模式 (ab)d(dc) 可以代表以下 4 种可能性中的任意一种：add、adc、bdd、bdc。

输入格式

第一行包含 3 个整数 $L$、$D$ 和 $N$，用空格分隔。接下来的 $D$ 行，每行包含一个长度为 $L$ 的单词。这些是已知存在于外星语言中的单词。随后是 $N$ 个测试用例，每个测试用例占一行，由上述模式组成。你可以假设所有给出的已知单词都是唯一的。

输出格式

对于每个测试用例，输出 Case #X: K，其中 $X$ 是测试用例编号（从 1 开始），$K$ 表示外星语言中有多少个单词与该模式匹配。

数据范围

小数据集（10 分）

$1 \le L \le 10$ $1 \le D \le 25$ $1 \le N \le 10$

大数据集（23 分）

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

样例

样例输入 1

3 5 4
abc
bca
dac
dbc
cba
(ab)(bc)(ca)
abc
(abc)(abc)(abc)
(zyx)bc

样例输出 1

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