$n$ 個の頂点を含む根なし木が与えられます。各頂点には色が塗られており、正の整数 $c_i$ が $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$）が含まれます。

2行目には、各頂点の色を表す $n$ 個の整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le n$）が含まれます。

続く $n - 1$ 行には、それぞれ木の辺を表す2つの整数 $u, v$（$1 \le u, v \le n, u \neq v$）が含まれます。これら $n - 1$ 本の辺が木構造をなすことが保証されています。

すべてのテストケースにおける $n$ の総和が $2 \times 10^5$ を超えないことが保証されています。

出力

各テストケースについて、順序対の個数を $998244353$ で割った余りを表す整数を1行に出力してください。

入出力例

入力例 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