Givet är ett orotat träd som innehåller $n$ noder, där varje nod har en färg som representeras av ett positivt heltal $c_i$ för den $i$-te noden.

Antag att $S$ och $T$ är mängder av noder i trädet. Ett ordnat par $(S, T)$ betraktas som giltigt om alla följande villkor är uppfyllda:

• Både $S$ och $T$ är icke-tomma mängder;
• Alla noder i $S$ har samma färg, och alla noder i $T$ har samma färg;
• Delgrafen $\text{sub}(S)$ för nodmängden $S$ definieras som den minsta sammanhängande delgrafen av trädet som innehåller nodmängden $S$, och på motsvarande sätt för $\text{sub}(T)$. Det krävs att $\text{sub}(S)$ och $\text{sub}(T)$ inte skär varandra, vilket innebär att de inte har några gemensamma noder eller kanter.

Bestäm antalet giltiga ordnade par $(S, T)$ modulo $998244353$. Observera att om $S \neq T$ så betraktas det ordnade paret $(S, T)$ som skilt från det ordnade paret $(T, S)$.

Indata

Detta problem innehåller flera testfall. Den första raden i indatan innehåller ett heltal $T$ ($1 \le T \le 10^4$), som representerar antalet testfall.

För varje testfall:

Den första raden innehåller ett heltal $n$ ($1 \le n \le 2 \times 10^5$), som representerar antalet noder i det orotade trädet.

Den andra raden innehåller $n$ heltal $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$), som representerar färgen på varje nod.

De följande $n - 1$ raderna innehåller var och en två heltal $u, v$ ($1 \le u, v \le n, u \neq v$), som representerar trädets kanter. Det garanteras att dessa $n - 1$ kanter bildar en trädstruktur.

Indatan garanterar att den totala summan av $n$ över alla testfall inte överstiger $2 \times 10^5$.

Utdata

För varje testfall, skriv ut en enda rad som innehåller ett heltal som representerar antalet ordnade par modulo $998244353$.

Exempel

Exempelindata 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

Exempelutdata 1

2
54
42