Gitt et urotet tre som inneholder $n$ noder, der hver node har en farge representert ved et positivt heltall $c_i$ for den $i$-te noden.

Anta at $S$ og $T$ er mengder av noder i treet. Et ordnet par $(S, T)$ regnes som gyldig hvis alle følgende betingelser er oppfylt:

• Både $S$ og $T$ er ikke-tomme mengder;
• Alle noder i $S$ har samme farge, og alle noder i $T$ har samme farge;
• Delgrafen $\text{sub}(S)$ til nodemengden $S$ er definert som den minste sammenhengende delgrafen av treet som inneholder nodemengden $S$, og tilsvarende for $\text{sub}(T)$. Det kreves at $\text{sub}(S)$ og $\text{sub}(T)$ ikke krysser hverandre, noe som betyr at de ikke har noen felles noder eller kanter.

Bestem antallet gyldige ordnede par $(S, T)$ modulo $998244353$. Merk at dersom $S \neq T$, regnes det ordnede paret $(S, T)$ som forskjellig fra det ordnede paret $(T, S)$.

Inndata

Denne oppgaven inneholder flere testtilfeller. Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T \le 10^4$), som representerer antallet testtilfeller.

For hvert testtilfelle:

Den første linjen inneholder et heltall $n$ ($1 \le n \le 2 \times 10^5$), som representerer antallet noder i det urotede treet.

Den andre linjen inneholder $n$ heltall $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$), som representerer fargen til hver node.

De neste $n - 1$ linjene inneholder hver to heltall $u, v$ ($1 \le u, v \le n, u \neq v$), som representerer kantene i treet. Det er garantert at disse $n - 1$ kantene danner en trestruktur.

Dataene garanterer at den totale summen av $n$ over alle testtilfeller ikke overstiger $2 \times 10^5$.

Utdata

For hvert testtilfelle skal du skrive ut én enkelt linje som inneholder et heltall som representerer antallet ordnede par modulo $998244353$.

Eksempel

Eksempelinndata 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

Eksempelutdata 1

2
54
42