J. Sichuan Provincial Contest
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are going to participate in the SCCPC.

You have found a tree with $$$n$$$ nodes, where each node has an uppercase English character attached to it. Let's denote the character attached to node $$$i$$$ as $$$S_i$$$.

You want to know how many simple paths containing exactly five nodes $$$u, v, x, y, z$$$ exist in this tree such that the sequence $$$S_u S_v S_x S_y S_z$$$ exactly forms the string SCCPC.

Input

The first line contains a positive integer $$$T$$$ $$$(1\leq T\leq 10^4)$$$, indicating the number of test cases.

For each test case, the first line contains an integer $$$n$$$ $$$(1\leq n\leq 10^6)$$$, representing the number of nodes in the tree.

The second line contains a string $$$S$$$ of length $$$n$$$, composed only of uppercase English letters, where the $$$i$$$-th character $$$S_i$$$ is the character attached to the $$$i$$$-th node of the tree.

The next $$$n-1$$$ lines each contain two integers $$$x_i, y_i$$$ $$$(1\leq x_i,y_i\leq n, x_i\neq y_i)$$$, indicating that there is an edge connecting nodes $$$x_i$$$ and $$$y_i$$$ in the tree.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2\times 10^6$$$.

Output

For each test case, output a single integer on a new line representing the number of simple paths.

Example
Input
2
5
SCCPC
1 2
2 3
3 4
4 5
7
SCCPCCC
1 2
2 3
3 4
4 5
4 6
4 7
Output
1
3