Annettuna on juureton puu, jossa on $n$ solmua, ja jokaisella solmulla on väri, jota kuvaa positiivinen kokonaisluku $c_i$ solmulle $i$.

Oletetaan, että $S$ ja $T$ ovat puun solmujen joukkoja. Järjestettyä paria $(S, T)$ pidetään kelvollisena, jos kaikki seuraavat ehdot täyttyvät:

• Sekä $S$ että $T$ ovat epätyhjiä joukkoja;
• Kaikilla joukon $S$ solmuilla on sama väri, ja kaikilla joukon $T$ solmuilla on sama väri;
• Solmujoukon $S$ aliverkko $\text{sub}(S)$ määritellään puun pienimmäksi yhtenäiseksi aliverkoksi, joka sisältää solmujoukon $S$, ja vastaavasti määritellään $\text{sub}(T)$. Vaaditaan, että $\text{sub}(S)$ ja $\text{sub}(T)$ eivät leikkaa toisiaan, mikä tarkoittaa, ettei niillä ole yhteisiä solmuja eikä kaaria.

Määritä kaikkien kelvollisten järjestettyjen parien $(S, T)$ lukumäärä modulo $998244353$. Huomaa, että jos $S \neq T$, järjestettyä paria $(S, T)$ pidetään eri parina kuin järjestettyä paria $(T, S)$.

Syöte

Tässä tehtävässä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^4$), joka ilmoittaa testitapausten lukumäärän.

Jokaiselle testitapaukselle:

Ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 2 \times 10^5$), joka ilmoittaa juurettoman puun solmujen lukumäärän.

Toinen rivi sisältää $n$ kokonaislukua $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$), jotka ilmoittavat kunkin solmun värin.

Seuraavat $n - 1$ riviä sisältävät kukin kaksi kokonaislukua $u, v$ ($1 \le u, v \le n, u \neq v$), jotka kuvaavat puun kaaria. On taattu, että nämä $n - 1$ kaarta muodostavat puurakenteen.

Data takaa, että lukujen $n$ kokonaissumma yli kaikkien testitapausten ei ylitä arvoa $2 \times 10^5$.

Tuloste

Tulosta jokaiselle testitapaukselle yksi rivi, joka sisältää kokonaisluvun: järjestettyjen parien lukumäärän modulo $998244353$.

Esimerkki

Esimerkkisyöte 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

Esimerkkituloste 1

2
54
42