Dane jest nieukorzenione drzewo zawierające $n$ wierzchołków, w którym każdy wierzchołek ma kolor reprezentowany przez dodatnią liczbę całkowitą $c_i$ dla $i$-tego wierzchołka.

Załóżmy, że $S$ i $T$ są zbiorami wierzchołków w drzewie. Para uporządkowana $(S, T)$ jest uznawana za poprawną, jeśli spełnione są wszystkie poniższe warunki:

• Zarówno $S$, jak i $T$ są zbiorami niepustymi;
• Wszystkie wierzchołki w $S$ mają ten sam kolor oraz wszystkie wierzchołki w $T$ mają ten sam kolor;
• Podgraf $\text{sub}(S)$ zbioru wierzchołków $S$ jest zdefiniowany jako najmniejszy spójny podgraf drzewa zawierający zbiór wierzchołków $S$, i analogicznie dla $\text{sub}(T)$. Wymagane jest, aby $\text{sub}(S)$ i $\text{sub}(T)$ nie przecinały się, co oznacza, że nie mają wspólnych wierzchołków ani krawędzi.

Wyznacz liczbę wszystkich poprawnych par uporządkowanych $(S, T)$ modulo $998244353$. Należy zauważyć, że jeśli $S \neq T$, to para uporządkowana $(S, T)$ jest uważana za różną od pary uporządkowanej $(T, S)$.

Wejście

To zadanie zawiera wiele przypadków testowych. Pierwszy wiersz wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 10^4$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego:

Pierwszy wiersz zawiera liczbę całkowitą $n$ ($1 \le n \le 2 \times 10^5$), oznaczającą liczbę wierzchołków w nieukorzenionym drzewie.

Drugi wiersz zawiera $n$ liczb całkowitych $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$), oznaczających kolor każdego wierzchołka.

Kolejne $n - 1$ wierszy zawiera po dwie liczby całkowite $u, v$ ($1 \le u, v \le n, u \neq v$), reprezentujące krawędzie drzewa. Gwarantowane jest, że te $n - 1$ krawędzi tworzy strukturę drzewa.

Dane gwarantują, że łączna suma $n$ we wszystkich przypadkach testowych nie przekracza $2 \times 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz pojedynczy wiersz zawierający jedną liczbę całkowitą, oznaczającą liczbę par uporządkowanych modulo $998244353$.

Przykład

Przykładowe wejście 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

Przykładowe wyjście 1

2
54
42