hdoj2222

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cstring>
#include <map>
#include <queue>
#include <set>
#include <cassert>
#include <stack>
#include <bitset>
//#include <unordered_set>
#define mkp make_pair
#define err cout<<"here"<<endl
using namespace std;
const double EPS=1e-12;
typedef long long lon;
typedef unsigned long long ull;
typedef map<ull,int>::iterator IT;
const lon SZ=500010,SSZ=1010,APB=26,mod=100000,one=97;
const lon INF=0x7FFFFFFF;
int n,m,cnt,nex[SZ][APB];
int mk[SZ],vst[SZ],in[SZ],used[SZ];
int fail[SZ];
struct nd{
    lon to,wt;
    nd(lon a=0,lon b=0):to(a),wt(b){}
};
char ch[2*SZ];

void add(int x)
{
    lon cur=0;
    for(lon i=1;ch[i];++i)
    {
        lon c=ch[i]-‘a‘;
        if(!nex[cur][c])nex[cur][c]=++cnt;
        cur=nex[cur][c];
    }
    ++mk[cur];
}

void build()
{
    queue<lon> q;
    q.push(0);
    for(;q.size();)
    {
        lon fr=q.front();
        q.pop();
        for(lon i=0;i<APB;++i)
        {
            lon t=nex[fr][i];
            if(t)
            {
                if(fr==0)fail[t]=0;
                else
                {
                    lon u=fail[fr];
                    for(;u&&!nex[u][i];u=fail[u]);
                    fail[t]=nex[u][i];

                    mk[t]+=mk[fail[t]];
                }
                q.push(t);
            }
        }
    }
}

lon get_nex(lon sta,lon c)
{
    for(;sta&&!nex[sta][c];sta=fail[sta]);
    return nex[sta][c];
}

void init()
{
    cin>>m;
    for(lon i=1;i<=m;++i)
    {
        cin>>ch+1;
        add(i);
    }
    build();
    cin>>ch+1;
    int cur=0;
    int res=0;
    for(int i=1;ch[i];++i)
    {
        int c=ch[i]-‘a‘;
        cur=get_nex(cur,c);
        vst[cur]=1;
        //if(!vst[cur])res+=mk[cur];
        //for(int u=cur;u;u=fail[u])
        //if(!vst[u])res+=mk[u],vst[u]=1;
        //cout<<i<<" "<<cur<<" "<<res<<endl;
    }
    queue<int> q;
    for(int i=1;i<=cnt;++i)++in[fail[i]];
    for(int i=1;i<=cnt;++i)
    {
        if(in[i]==0)
        {
            q.push(i);
        }
    }
    for(;q.size();)
    {
        int fr=q.front();
        q.pop();
        if(vst[fr])
        {
            for(int u=fr;u;u=fail[u])
            {
                if(!used[u])res+=mk[u]-mk[fail[u]],used[u]=1;
                vst[u]=0;
            }
        }
        
        if(--in[fail[fr]]==0&&fail[fr])
        {
            q.push(fail[fr]);
        }
    }
    for(int i=1;i<=cnt;++i)
    {
        
    }
    for(int i=1;i<=cnt;++i)
    {
        //cout<<i<<" "<<mk[i]<<endl;
    }
    cout<<res<<endl;
}

void work()
{
    
}

void release()
{    
    for(int i=0;i<=cnt;++i)
    {
        mk[i]=vst[i]=in[i]=used[i]=0;
        memset(nex[i],0,sizeof(nex[i]));
    }
    cnt=0;
}

int main()
{
    std::ios::sync_with_stdio(0);
    //freopen("d:\\1.txt","r",stdin);
    lon casenum;
    cin>>casenum;
    //cout<<casenum<<endl;
    for(lon time=1LL;time<=casenum;++time)
    //for(lon time=1;cin>>m>>n;++time)
    {
        init();
        work();
        release();
    }
    return 0;
}