È dato un albero non radicato contenente $n$ nodi, in cui ogni nodo ha un colore rappresentato da un intero positivo $c_i$ per l'$i$-esimo nodo.

Supponiamo che $S$ e $T$ siano insiemi di nodi nell'albero. Una coppia ordinata $(S, T)$ è considerata valida se sono soddisfatte tutte le seguenti condizioni:

• Sia $S$ che $T$ sono insiemi non vuoti;
• Tutti i nodi in $S$ hanno lo stesso colore e tutti i nodi in $T$ hanno lo stesso colore;
• Il sottografo $\text{sub}(S)$ dell'insieme di nodi $S$ è definito come il più piccolo sottografo connesso dell'albero che contiene l'insieme di nodi $S$, e analogamente per $\text{sub}(T)$. Si richiede che $\text{sub}(S)$ e $\text{sub}(T)$ non si intersechino, cioè che non abbiano nodi o archi in comune.

Determina il numero di tutte le coppie ordinate valide $(S, T)$ modulo $998244353$. Si noti che se $S \neq T$, allora la coppia ordinata $(S, T)$ è considerata diversa dalla coppia ordinata $(T, S)$.

Input

Questo problema contiene più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 10^4$), che rappresenta il numero di casi di test.

Per ciascun caso di test:

La prima riga contiene un intero $n$ ($1 \le n \le 2 \times 10^5$), che rappresenta il numero di nodi nell'albero non radicato.

La seconda riga contiene $n$ interi $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$), che rappresentano il colore di ciascun nodo.

Le successive $n - 1$ righe contengono ciascuna due interi $u, v$ ($1 \le u, v \le n, u \neq v$), che rappresentano gli archi dell'albero. È garantito che questi $n - 1$ archi formino una struttura ad albero.

I dati garantiscono che la somma totale di $n$ su tutti i casi di test non superi $2 \times 10^5$.

Output

Per ciascun caso di test, stampa una singola riga contenente un intero, che rappresenta il numero di coppie ordinate modulo $998244353$.

Esempio

Input di esempio 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

Output di esempio 1

2
54
42