1 #include<stdio.h> 2 #include<queue> 3 #include<cstring> 4 #define go(i,a,b) for(int i=a;i<=b;i++) 5 using namespace std;const int N=1000004; 6 int f[N],last[N],ch[N][26],sz,ans,val[N]; 7 void Insert(char *s){ 8     int n=strlen(s+1),u=0;go(i,1,n){int c=s[i]-‘a‘;if(!ch[u][c]) 9     {val[ch[u][c]=++sz]=0;go(j,0,25)ch[sz][j]=0;}u=ch[u][c];}val[u]++;10 }11 void Fail(){12     queue<int>q;go(c,0,25){int u=ch[0][c];if(!u)continue;last[u]=f[u]=0;q.push(u);}13     while(!q.empty()){int r=q.front();q.pop();go(c,0,25){14         int u=ch[r][c];if(!u){ch[r][c]=ch[f[r]][c];continue;}15         q.push(u);f[u]=ch[f[r]][c];last[u]=val[f[u]]?f[u]:last[f[u]];}}16 }17 void Find(char *s){18     int n=strlen(s+1),v=0;go(i,1,n){19     int c=s[i]-‘a‘;if(v&&!ch[v][c])v=f[v];20     int t=v=ch[v][c];while(t){ans+=val[t];val[t]=0;t=last[t];}}21 }22 int main(){char s[N];int T,n;scanf("%d",&T);while(T--&&scanf("%d",&n)){23     sz=ans=0;go(i,0,25)ch[0][i]=0;24     go(i,1,n)scanf("%s",s+1),Insert(s);25     Fail();scanf("%s",s+1);Find(s);printf("%d\n",ans);26 }return 0;}//Paul_Guderian