Description

奇奇通过了层层关卡，传说中的藏宝洞也逐渐揭开了层层面纱。可是就在路上，奇奇在一个不起眼的角落，发现了一个刻有未知古文的立方体。看着斑驳的立方体上面复杂的古老文字，奇奇不禁想到了那些古老的隐秘。反复地观看这些文字，突然奇奇在立方体上看到了一个人的名字:哥尔·D·罗杰。这让奇奇知道了这些古文是关于那空白的一百年的历史。

现在奇奇想看能否从中探究出某些秘辛，因为奇奇之前对古文还有有些了解的，所以他知道一些古文的关键词。已知现在立方体上的古文完全由26个小写英文字母组成,并且小写字母个数为 n (0<n<=1000000)。奇奇所知道的关键词个数为 m (0<=m<=10001)同样由小写字母组成，且每个关键词互不相同，所包含的字母个数为 ai (0<ai<=50)。已知每一个关键词的单位参考价值由它所有前缀集合中是否存在其他关键词决定，若一个关键词的前缀集合中不存在其他关键词，则其单位价值为 1，反之若集合中存在其他的关键词，那么该关键词的单位价值为( 1 + 该关键词前缀集合中存在的其他关键词数目)。每一个关键词所能带给奇奇的考古参考价值为(关键词单位参考价值 * 关键词在立方体古文中出现的次数)，现在奇奇想知道这些关键词总共能带给他带来多大的考古价值？

Format

Input

输入数据有多组，每组数据的第一行包括了一个正整数 T (0< T < 5)，代表 T 个测试。

对于每个测试：第一行包括一个数字 m (含义如题)。

接下来的 m 行每行有一个字符串分别代表奇奇所知道的 m 个关键词。

第 m + 1 行同样是一个字符串代表了立方体上的古文。

Output

对于每个测试输出一行：包括一个数字代表着 m 个关键词所包含的总的考古价值。

Samples

1
2
bb
aaa
bbaaa
1
2
a
aa
aa

2
4

Hint