温馨提示：SDOI 2016 二轮省选现场不开栈。

给出 $ n $ 个结点的树结构 $ T $，其中每一个结点上有一个字符，这里我们所说的字符只考虑大写字母 A 到 Z ，再给出长度为 $ m $ 的模式串 $ S $，其中每一位仍然是 A 到 Z 的大写字母。

Alice 希望知道，有多少对结点 $\langle u, v \rangle$ 满足 $ T $ 上从 $ u $ 到 $ v $ 的最短路径形成的字符串可以由模式串 $ S $ 重复若干次得到？这里结点对 $\langle u,v \rangle$是有序的，也就是说 $\langle u, v \rangle$ 和 $\langle v, u \rangle$ 需要被区分。所谓模式串的重复，是将若干个模式串 $ S $ 依次相接（不能重叠）。例如当 $ S = $PLUS 的时候，重复两次会得到 PLUSPLUS，重复三次会得到 PLUSPLUSPLUS。同时要注意，重复必须是整数次的。例如当 $S=$XYXY 时，因为必须重复整数次，所以 XYXYXY 不能看作是 $ S $ 重复若干次得到的。

输入格式

每一个数据有多组测试，

第一行输入一个整数 $ C $，表示总的测试个数。

对于每一组测试来说：

• 第一行输入两个整数，分别表示树 $T$ 的结点个数 $n$ 与模式长度 $m$。结点被依次编号为 $1$ 到 $n$；
• 之后一行，依次给出了 $n$ 个大写字母（以一个长度为 $n$ 的字符串的形式给出），依次对应树上每一个结点上的字符（第 $i$ 个字符对应了第 $i$ 个结点)。
• 之后 $n-1$ 行，每行有两个整数 $u$ 和 $v$ 表示树上的一条无向边，之后一行给定一个长度为 $m$ 的由大写字母组成的字符串，为模式串 $S$。

输出格式

给出 $C$ 行，对应 $C$ 组测试。每一行输出一个整数，表示有多少对节点 $\langle u,v \rangle$ 满足从 $u$ 到 $v$ 的路径形成的字符串恰好是模式串的若干次重复。

样例数据

样例输入

1
11 4
IODSSDSOIOI
1 2
2 3
3 4
1 5
5 6
6 7
3 8
8 9
6 10
10 11
SDOI

样例输出

5

子任务

• Subtask 1(20 points): $n \leq 3000$
• Subtask 2(80 points): 没有额外的限制

对于所有的数据，$1 \leq C \leq 10$，$\ 1 \leq n \leq 100\,000$，$1 \leq m \leq 20$。