SP108 MORSE - Decoding Morse Sequences

从前有一种“二进制”代码，叫摩尔斯电码，在这种电码里面有两种符号，为短脉冲（用“.”表示）和长脉冲（用“-”表示），26 个字符对应的编码如下表： ``` A .- B -... C -.-. D -.. E . F ..-. G --. H .... I .. J .--- K -.- L .-.. M -- N -. O --- P .--. Q --.- R .-. S ... T - U ..- V ...- W .-- X -..- Y -.-- Z --.. ``` 但是，同一种摩尔斯编码可能有多种解释，比如-.-..-可以解释为 CAT 和 NXT 。 你现在要完成如下任务： 读取一个摩尔斯序列和一本“字典”。 计算出仅用“字典”中的单词时，这个摩尔斯序列会有多少种解码方式。

第一行一个整数 $d$ ，表示数据的数量。 每组数据第一行包含一个字符串，即摩尔斯序列。 然后有一行一个整数 $n$ ，表示“字典”里所包含的单词数。 接下来 $n$ 行，每行一个字符串，表示字典里面的一个单词

输出 $d$ 行，每行一个整数，第 $i$ 个整数表示第 $i$ 组测试数据里面有多少种解码方式。 ### 数据规模 $1 \le d \le 20$ ， $1 \le $摩尔斯电码的长度$ \le 10^4$ ， $1 \le n \le 10^4$ ， $1 \le $每个单词的长度$ \le 20$ ，且每个单词中只有 26 个大写字母 ， 所求答案$ \le 2 \times 10^9$ 。