昵称检索

Problem Description

给定一个字符串 $S$，请计算从中删去一部分字符后（可以什么都不删），可以得到多少个本质不同的''昵称''。 一个字符串被认为是''昵称''当且仅当它可以被划分成前后两个部分，第一个部分是给定的 $n$ 个名字之一，第二个部分长度固定四位，表示生日。 例如第一个样例中，可以得到的''昵称''分别为：''$\texttt{kevin0724}$''、''$\texttt{kevin0729}$''、''$\texttt{kevin0924}$''、''$\texttt{kevin0929}$''。

Input

第一行包含一个正整数 $T$ ($1\leq T\leq 100$)，表示测试数据的组数。 每组数据第一行包含两个正整数 $n,m$ ($1\leq n\leq 10^5$, $1\leq m\leq 10^6$)，分别表示名字的数量以及字符串 $S$ 的长度。 第二行包含一个长度为 $m$ 的字符串 $S$，由数字和小写英文字母构成。 接下来 $n$ 行，每行一个长度在 $[1,20]$ 之间的仅由小写英文字母构成的字符串 $name_i$，表示一个名字。输入数据保证名字两两不同。 输入数据保证 $\sum m\leq 7\,000\,000$，且 $\sum |name|\leq 7\,000\,000$。

Output

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

Sample Input

2
1 18
k9e9v9i9n909792949
kevin
2 24
alicealicebobbob02290229
alice
bob

Sample Output

4
18

Source

2024“钉耙编程”中国大学生算法设计超级联赛（4）