给定一棵包含 $n$ 个节点的无根树，其中每个节点都有一个颜色，第 $i$ 个节点的颜色用正整数 $c_i$ 表示。

假设 $S$ 和 $T$ 是树中的节点集合。如果满足以下所有条件，则称有序对 $(S, T)$ 是合法的：

• $S$ 和 $T$ 都是非空集合；
• $S$ 中的所有节点颜色相同，且 $T$ 中的所有节点颜色相同；
• 节点集合 $S$ 的子图 $\text{sub}(S)$ 定义为包含节点集合 $S$ 的最小连通子图，对于 $\text{sub}(T)$ 也是类似的定义。要求 $\text{sub}(S)$ 和 $\text{sub}(T)$ 不相交，即它们没有公共的节点或边。

求所有合法有序对 $(S, T)$ 的数量模 $998244353$ 的值。需要注意的是，如果 $S \neq T$，则有序对 $(S, T)$ 被认为与有序对 $(T, S)$ 不同。

输入格式

本题包含多组测试数据。输入的第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试数据的组数。

对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$)，表示无根树中的节点数。

第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$)，表示每个节点的颜色。

接下来的 $n - 1$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n, u \neq v$)，表示树的一条边。保证这 $n - 1$ 条边构成一棵树。

数据保证所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示模 $998244353$ 后的合法有序对数量。

样例

输入样例 1

3
2
1 1
1 2
5
1 1 1 2 2
1 2
2 3
3 4
4 5
5
1 2 1 2 1
1 2
1 3
2 4
2 5

输出样例 1

2
54
42