On vous donne un arbre non enraciné contenant $n$ nœuds, où chaque nœud possède une couleur représentée par un entier strictement positif $c_i$ pour le $i$-ème nœud.

Supposons que $S$ et $T$ soient des ensembles de nœuds de l'arbre. Un couple $(S, T)$ est considéré comme valide si toutes les conditions suivantes sont réunies :

• $S$ et $T$ sont tous deux des ensembles non vides ;
• Tous les nœuds de $S$ ont la même couleur, et tous les nœuds de $T$ ont la même couleur ;
• Le sous-graphe $\text{sub}(S)$ de l'ensemble de nœuds $S$ est défini comme le plus petit sous-graphe connexe de l'arbre qui contient l'ensemble de nœuds $S$, et de même pour $\text{sub}(T)$. On exige que $\text{sub}(S)$ et $\text{sub}(T)$ ne s'intersectent pas, c'est-à-dire qu'ils n'aient aucun nœud ni aucune arête en commun.

Déterminez le nombre de tous les couples valides $(S, T)$ modulo $998244353$. Notez que si $S \neq T$, alors le couple $(S, T)$ est considéré comme différent du couple $(T, S)$.

Entrée

Ce problème contient plusieurs jeux de tests. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 10^4$), représentant le nombre de jeux de tests.

Pour chaque jeu de tests :

La première ligne contient un entier $n$ ($1 \le n \le 2 \times 10^5$), représentant le nombre de nœuds dans l'arbre non enraciné.

La deuxième ligne contient $n$ entiers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$), représentant la couleur de chaque nœud.

Les $n - 1$ lignes suivantes contiennent chacune deux entiers $u, v$ ($1 \le u, v \le n, u \neq v$), représentant les arêtes de l'arbre. Il est garanti que ces $n - 1$ arêtes forment une structure d'arbre.

Les données garantissent que la somme totale de $n$ sur l'ensemble des jeux de tests ne dépasse pas $2 \times 10^5$.

Sortie

Pour chaque jeu de tests, affichez une seule ligne contenant un entier, représentant le nombre de couples modulo $998244353$.

Exemple

Entrée d'exemple 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

Sortie d'exemple 1

2
54
42