Gefið er órótað tré sem inniheldur $n$ hnúta, þar sem hver hnútur hefur lit sem táknar er með jákvæðri heiltölu $c_i$ fyrir $i$-ta hnútinn.

Gerum ráð fyrir að $S$ og $T$ séu mengi hnúta í trénu. Röðuð tvennd $(S, T)$ telst gild ef öll eftirfarandi skilyrði eru uppfyllt:

• Bæði $S$ og $T$ eru ótóm mengi;
• Allir hnútar í $S$ hafa sama lit og allir hnútar í $T$ hafa sama lit;
• Hlutnetið $\text{sub}(S)$ fyrir hnútamengið $S$ er skilgreint sem minnsta samanhangandi hlutnet trésins sem inniheldur hnútamengið $S$, og á sama hátt fyrir $\text{sub}(T)$. Krafist er að $\text{sub}(S)$ og $\text{sub}(T)$ skerist ekki, sem þýðir að þau hafi enga sameiginlega hnúta né leggi.

Ákvarðið fjölda allra gildra raðaðra tvennda $(S, T)$ módúló $998244353$. Athugið að ef $S \neq T$, þá telst raðaða tvenndin $(S, T)$ ólík röðuðu tvenndinni $(T, S)$.

Inntak

Þetta verkefni inniheldur mörg prófunartilvik. Fyrsta lína inntaksins inniheldur heiltölu $T$ ($1 \le T \le 10^4$), sem táknar fjölda prófunartilvika.

Fyrir hvert prófunartilvik:

Fyrsta línan inniheldur heiltölu $n$ ($1 \le n \le 2 \times 10^5$), sem táknar fjölda hnúta í órótaða trénu.

Önnur línan inniheldur $n$ heiltölur $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$), sem tákna lit hvers hnúts.

Næstu $n - 1$ línur innihalda hver um sig tvær heiltölur $u, v$ ($1 \le u, v \le n, u \neq v$), sem tákna leggi trésins. Tryggt er að þessir $n - 1$ leggir myndi trjábyggingu.

Gögnin tryggja að heildarsumma $n$ yfir öll prófunartilvik fari ekki yfir $2 \times 10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur heiltölu sem táknar fjölda raðaðra tvennda módúló $998244353$.

Dæmi

Sýnidæmi inntaks 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

Sýnidæmi úttaks 1

2
54
42