給定一棵包含 $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