Before the digital age, the most common ``binary'' code for radio communication was the Morse code. In Morse code, symbols are encoded as sequences of short and long pulses (called dots and dashes, respectively). The following table reproduces the Morse code for the alphabet, where dots and dashes are represented by ASCII characters ``.'' and ``-'':

Notice that in the absence of pauses between letters there might be multiple interpretations of a Morse sequence. For example, the sequence ``-.-..--'' can be decoded both as ``CAT'' or ``NXT'' (among others). A human Morse operator would use other context information (such as a language dictionary) to decide the appropriate decoding.

Write a program that reads a Morse code string and a list of words (a dictionary) and attempts to parse the Morse code into a phrase using words that occur in the dictionary. The program's output should be the number of distinct phrases that can be obtained.

Notice that we are interested in full matches, i.e. the complete Morse string must be matched to words in the dictionary.

Input 

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The input starts with the Morse code string, made up of characters ``.'' and ``-'', with no spaces between them, and terminated by the end-of-line character.

The next line consists of the number N of words in the dictionary, and is followed by N dictionary words, one in each line. Each word consists of upper-case characters from ``A'' to ``Z'' only.

The number of words in the dictionary is less than or equal to 10000 and the Morse code string is at most 1000 characters long.

Output 

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

The output should be a single integer number representing the count of distinct phrases into which the Morse code can be parsed. You may assume that this number is at most 2 × 10⁹.

Sample Input 

1

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

Sample Output 

2

题意：将下面给的字符串转成编码，问完全由下面的字符串组成给定编码一共有多少种情况。解释样例：第一种为ATTACK+DAWN，第二种为AT+TACK+DAWN。

思路：先用KMP求出每个小的字符串匹配之处，然后dp很简单。

AC代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{ int len,pos;
}box[10001000];
bool cmp(node a,node b)
{ return a.pos<b.pos;
}
char s[26][5]={".-","-...","-.-.","-..",
               ".","..-.","--.","....",
               "..",".---","-.-",".-..",
               "--","-.","---",".--.",
               "--.-",".-.","...","-",
               "..-","...-",".--","-..-",
               "-.--","--.."};
char P[100010],str[100010],s2[10010];
int f[100010],num,dp[10010];
void getFail()
{ int m=strlen(P),i,j;
  f[0]=0;f[1]=0;
  for(i=1;i<m;i++)
  { j=f[i];
    while(j && P[i]!=P[j])
     j=f[j];
    if(P[i]==P[j])
     f[i+1]=j+1;
    else
     f[i+1]=0;
  }
}
void Find()
{ int n,m,i,j=0;
  n=strlen(str);
  m=strlen(P);
  getFail();
  for (i=0;i<n;i++)
  { while(j && P[j]!=str[i])
     j=f[j];
    if(P[j]==str[i])
     j++;
    if(j==m)
    { box[++num].len=m;
      box[num].pos=i-m+1;
    }
  }
}
int main()
{ int T,t,n,m,len1,i,j,k;
  scanf("%d",&T);
  for(t=1;t<=T;t++)
  { scanf("%s",str);
    n=strlen(str);
    scanf("%d",&m);
    memset(dp,0,sizeof(dp));
    dp[0]=1;
    num=0;
    while(m--)
    { scanf("%s",s2);
      len1=strlen(s2);
      P[0]='\0';
      for(i=0;i<len1;i++)
       strcat(P,s[s2[i]-'A']);
      Find();
    }
    sort(box+1,box+1+num,cmp);
    for(i=1;i<=num;i++)
     dp[box[i].pos+box[i].len]+=dp[box[i].pos];
    if(t!=1)
     printf("\n");
    printf("%d\n",dp[n]);
  }
}