题目描述

你要参加 SCCPC 了。

你找到了一棵 $n$ 个点的树，树上的每个点都挂了一个英文大写字符，不妨记点 $i$ 挂的字符是 $S_i$。

你想知道这棵树上有多少条包含恰好五个点的简单路径 $u, v, x, y, z$，使得 $S_u S_v S_x S_y S_z$ 按顺序写出来刚好是字符串 SCCPC。

输入格式

第一行一个正整数 $T$（$1 \leq T \leq 10^4$），表示数据组数。

对于每组数据，第一行一个整数 $n$（$1 \leq n \leq 10^6$），表示树的点数。

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

接下来 $n - 1$ 行，每行两个整数 $x_i, y_i$（$1 \leq x_i, y_i \leq n, x_i \neq y_i$），表示树上有一条连接点 $x_i$ 和 $y_i$ 的边。

保证单个测试点内每组数据中 $n$ 的和不超过 $2 \times 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