题目描述

你要参加 $SCCPC$ 了。 你找到了一棵 $n$ 个点的树，树上的每个点都挂了一个英文大写字符，不妨记点 $i$ 挂的字符是 $S_i。$ 你想知道这棵树上有多少条包含恰好五个点的简单路径 $u, v, x, y, z$，使得 $S_u,S_v,S_x,S_y,S_z$ 按顺序写出来刚好是字符串 $SCCPC。$

输入格式

第一行一个正整数 $T (1 ≤ T ≤ 10^4 )$，表示数据组数。

对于每组数据，第一行一个整数 $n (1 ≤ n ≤ 10^6 )$，表示树的点数。

第二行一个长度为 $n$ 的仅由大写英文字母构成的字符串 $S$，字符串的第 $i$ 个字符 $S_i$ 即树上第 $i$ 个点挂 的字符。

接下来 $n − 1$ 行，每行两个整数 $x_i, y_i \quad (1 \le x_i, y_i \le n,\ x_i \ne y_i)$ ，表示树上有一条连接点 $x_i$ 和 $y_i$ 的边。

保证单个测试点内每组数据中 $n$ 的和不超过 $2 × 10^6。$

输出格式

对于每组数据，一行一个整数表示简单路径的数量。

输入样例:

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

输出样例：

1
3