Se da un árbol sin raíz que contiene $n$ nodos, donde cada nodo tiene un color representado por un entero positivo $c_i$ para el $i$-ésimo nodo.

Supongamos que $S$ y $T$ son conjuntos de nodos en el árbol. Un par ordenado $(S, T)$ se considera válido si se cumplen todas las condiciones siguientes:

• Tanto $S$ como $T$ son conjuntos no vacíos;
• Todos los nodos en $S$ tienen el mismo color, y todos los nodos en $T$ tienen el mismo color;
• El subgrafo $\text{sub}(S)$ del conjunto de nodos $S$ se define como el subgrafo conexo más pequeño del árbol que contiene al conjunto de nodos $S$, y de manera similar para $\text{sub}(T)$. Se requiere que $\text{sub}(S)$ y $\text{sub}(T)$ no se intersequen, lo que significa que no tienen nodos ni aristas en común.

Determina el número de todos los pares ordenados válidos $(S, T)$ módulo $998244353$. Cabe señalar que si $S \neq T$, entonces el par ordenado $(S, T)$ se considera diferente del par ordenado $(T, S)$.

Entrada

Este problema contiene múltiples casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1 \le T \le 10^4$), que representa el número de casos de prueba.

Para cada caso de prueba:

La primera línea contiene un entero $n$ ($1 \le n \le 2 \times 10^5$), que representa el número de nodos en el árbol sin raíz.

La segunda línea contiene $n$ enteros $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$), que representan el color de cada nodo.

Las siguientes $n - 1$ líneas contienen cada una dos enteros $u, v$ ($1 \le u, v \le n, u \neq v$), que representan las aristas del árbol. Se garantiza que estas $n - 1$ aristas forman una estructura de árbol.

Los datos garantizan que la suma total de $n$ en todos los casos de prueba no supera $2 \times 10^5$.

Salida

Para cada caso de prueba, imprime una sola línea que contenga un entero, representando el número de pares ordenados módulo $998244353$.

Ejemplo

Entrada de ejemplo 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

Salida de ejemplo 1

2
54
42