//ac自动机 可以优化成 trie图
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010, S = 55, M = 1000010;
int n;
//tire 以每个节点结尾的单词数量
int tr[N * S][26], cnt[N * S], idx;
//字符串
char str[M];
//宽搜
int q[N * S], ne[N * S];
void insert() {
//根节点
int p = 0;
//从头遍历,直到遍历到空
for (int i = 0; str[i]; i ++ ) {
//减去偏移量
int t = str[i] - 'a';
//如果不存在,就创建
if (!tr[p][t])
tr[p][t] = ++ idx;
//这条路就有了,直接走过去
p = tr[p][t];
}
//以p结尾的单词数量++
cnt[p] ++ ;
}
//构建ac自动机
//宽搜
void build() {
int hh = 0, tt = -1;
//宽搜 前两层都知道,就直接指向根节点
//因此从第一层开始,把根的所有儿子放进来
for (int i = 0; i < 26; i ++ )
//如果这个儿子存在
if (tr[0][i])
//入队
q[ ++ tt] = tr[0][i];
//宽搜
while (hh <= tt) {
//队头
int t = q[hh ++ ];
//遍历所有儿子
for (int i = 0; i < 26; i ++ ) {
//p是
//p对应kmp中的i
int p = tr[t][i];
//如果不存在
//指向父节点的next指针的位置
//相当于直接跳到应该走到的位置,避免多次跳,降低时间复杂度
if (!p)
tr[t][i] = tr[ne[t]][i];
//如果存在
else {
//等价while循环
ne[p] = tr[ne[t]][i];
//再加到队列中
q[ ++ tt] = p;
}
}
}
}
int main() {
int T;
scanf("%d", &T);
while (T -- ) {
memset(tr, 0, sizeof tr);
memset(cnt, 0, sizeof cnt);
memset(ne, 0, sizeof ne);
idx = 0;
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) {
//读入每个单词
scanf("%s", str);
//插入单词
insert();
}
//构建ac自动机
build();
scanf("%s", str);
int res = 0;
//匹配和原来kmp差不多
//j从根节点传进来
for (int i = 0, j = 0; str[i]; i ++ ) {
//字母
int t = str[i] - 'a';
j = tr[j][t];
int p = j;
while (p) {
res += cnt[p];
//每个单词只能加一次,所以要清零
cnt[p] = 0;
//往下
p = ne[p];
}
}
printf("%d
", res);
}
return 0;
}