描述

在数字时代之前，无线电通信中最常见的“二进制”代码是摩尔斯电码。在摩尔斯电码中，符号被编码为短脉冲和长脉冲（分别称为“点”和“划”）的序列。下表展示了字母的摩尔斯电码，其中点和划分别用ASCII字符“.”和“-”表示：

需要注意的是，如果字母之间没有停顿，一个摩尔斯序列可能有多种解释。例如，序列 -.-..-- 可以解码为 CAT 或 NXT（以及其他组合）。人类操作员会利用其他上下文信息（如语言字典）来确定正确的解码方式。但即使提供了字典，从一个摩尔斯序列中仍可能得到多个不同的短语。

任务

编写一个程序，对每个数据集：

读取一个摩尔斯序列和一个单词列表（字典）；
计算使用字典中的单词从给定摩尔斯序列中可以得到的不同短语的数量；
输出结果。

注意，我们要求完全匹配，即整个摩尔斯序列必须完全由字典中的单词匹配组成。

输入

输入的第一行包含一个正整数 $d$，表示数据集的数量，$1 \leq d \leq 20$。接下来是数据集的具体内容。

每个数据集的第一行是一个摩尔斯序列——一个非空字符串，由最多 $10\,000$ 个字符“.”和“-”组成，中间没有空格。

第二行包含一个整数 $n$，$1 \leq n \leq 10\,000$，表示字典中的单词数量。接下来的 $n$ 行每行包含一个字典单词——一个非空字符串，由最多 $20$ 个大写字母（从“A”到“Z”）组成。字典中不会出现重复的单词。

输出

输出应包含 $d$ 行，每行对应一个数据集的结果。第 $i$ 行应输出一个整数，表示第 $i$ 个数据集的摩尔斯序列可以解析出的不同短语的数量。你可以假设每个数据集的这一数值不超过 $2 \times 10^9$。

输入样例 1

1
.---.--.-.-.-.---...-.---.
6
AT
TACK
TICK
ATTACK
DAWN
DUSK

输出样例 1

2

来源

中欧 2001