畀定一棵包含 $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$），代表無根樹入面嘅節點數量。

第二行包含 $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