Reminder: Stack size is not increased during the SDOI 2016 second round provincial selection.

Given a tree $T$ with $n$ nodes, where each node contains a character (only uppercase letters A through Z are considered), and a pattern string $S$ of length $m$ (also consisting of uppercase letters A through Z).

Alice wants to know how many ordered pairs of nodes $\langle u, v \rangle$ exist such that the string formed by the shortest path from $u$ to $v$ on $T$ can be obtained by repeating the pattern string $S$ a certain number of times. The pair $\langle u, v \rangle$ is ordered, meaning $\langle u, v \rangle$ and $\langle v, u \rangle$ are distinct. Repeating the pattern string means concatenating several copies of $S$ (without overlap). For example, if $S = $ PLUS, repeating it twice yields PLUSPLUS, and repeating it three times yields PLUSPLUSPLUS. Note that the repetition must be an integer number of times. For example, if $S = $ XYXY, the string XYXYXY cannot be considered as a repetition of $S$ because it is not an integer multiple.

Input

Each dataset contains multiple test cases.

The first line contains an integer $C$, representing the total number of test cases.

For each test case:

• The first line contains two integers, $n$ and $m$, representing the number of nodes in the tree $T$ and the length of the pattern string, respectively. The nodes are numbered from $1$ to $n$.
• The next line provides $n$ uppercase letters (as a string of length $n$), corresponding to the characters on each node (the $i$-th character corresponds to the $i$-th node).
• The next $n-1$ lines each contain two integers $u$ and $v$, representing an undirected edge in the tree.
• The final line provides a string of length $m$ consisting of uppercase letters, which is the pattern string $S$.

Output

Output $C$ lines, corresponding to the $C$ test cases. Each line should contain a single integer representing the number of pairs of nodes $\langle u, v \rangle$ such that the string formed by the path from $u$ to $v$ is exactly an integer number of repetitions of the pattern string $S$.

Examples

Input 1

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

Output 1

5

Subtasks

• Subtask 1 (20 points): $n \leq 3000$
• Subtask 2 (80 points): No additional constraints

For all data, $1 \leq C \leq 10$, $1 \leq n \leq 100\,000$, $1 \leq m \leq 20$.