题目描述

给定一个字符串 $S$，请计算从中删去一部分字符后（可以什么都不删），可以得到多少个本质不同的''昵称''。

一个字符串被认为是''昵称''当且仅当它可以被划分成前后两个部分，第一个部分是给定的 $n$ 个名字之一，第二个部分长度固定四位，表示生日。

例如第一个样例中，可以得到的''昵称''分别为：$\text{kevin0724}、\text{kevin0729}、\text{kevin0924}、\text{kevin0929}$。

输入格式

第一行包含一个正整数 $T$ ($1≤T≤100$)，表示测试数据的组数。

每组数据第一行包含两个正整数 $n,m$ ($1≤n≤10^5, 1≤m≤10^6$)，分别表示名字的数量以及字符串 $S$ 的长度。

第二行包含一个长度为 $m$ 的字符串 $S$，由数字和小写英文字母构成。

接下来 $n$ 行，每行一个长度在 $[1,20]$ 之间的仅由小写英文字母构成的字符串 $name_i$，表示一个名字。输入数据保证名字两两不同。

输入数据保证 $∑m≤7000000$，且 $∑|name|≤7000000$。

输出格式

对于每组数据输出一行一个整数，即能得到的本质不同的''昵称''数量。

输入样例

2
1 18
k9e9v9i9n909792949
kevin
2 24
alicealicebobbob02290229
alice
bob

输出样例

4
18