Huomaa alipuun ja halkaisijan epätavallinen määritelmä tässä tehtävässä.

Tässä on joitakin määritelmiä:

• Puun $T$ koko on sen solmujen lukumäärä eli $|V(T)|$.
• Puun $T$ solmun $i$ aste on siihen kytkettyjen kaarien lukumäärä, jota merkitään $\operatorname{deg}_i$.
• Puu $T'$ on puun $T$ alipuu, jos ja vain jos:
  • Kaikille solmuille $v \in V(T')$ pätee $v \in V(T)$.
  • Kaikille kaarille $e \in E(T')$ pätee $e \in E(T)$.
• Olkoon $S_T$ puun $T$ alipuiden joukko.
• Puun $T$ halkaisija on puun $T$ suurimman sellaisen alipuun koko, jossa $\max(\operatorname{deg}_i) \le 2$.
• Olkoon $R_x$ suurimpien sellaisten puiden joukko, joille:
  • $\max(\operatorname{deg}_i) \le 3$.
  • Puun halkaisija on $2x$.
• Puulle $T$ olkoon $f(T)$ suurin $k$ siten, että $S_T \cap R_k \ne \emptyset$. Jos tällaista lukua $k$ ei ole, $f(T) = 0$.

Sinulle annetaan $n$-solmuinen puu $T$. Laske lukujen $f(T')$ summa yli kaikkien puun $T$ alipuiden $T'$ modulo $998244353$. Kaksi alipuuta ovat erilaisia, jos ja vain jos niillä on eri solmujoukko tai eri kaarijoukko.

Syöte

Jokainen testi sisältää useita testitapauksia. Ensimmäinen rivi sisältää yhden kokonaisluvun $t$ ($1 \le t \le 5 \times 10^4$), joka ilmaisee testitapausten lukumäärän. Seuraavaksi tulee testitapausten kuvaus.

Ensimmäinen rivi sisältää yhden kokonaisluvun $n$ ($1 \le n \le 10^5$, $\sum n \le 10^6$), joka ilmaisee puun $T$ solmujen lukumäärän.

Jokainen seuraavista $n - 1$ rivistä sisältää kaksi kokonaislukua $u, v$ ($1 \le u \ne v \le n$), jotka ilmaisevat puun $T$ kaaren.

Tuloste

Tulosta jokaiselle testitapaukselle yksi kokonaisluku, joka ilmaisee lukujen $f(T')$ summan modulo $998244353$.

Esimerkki

Syöte

2
5
1 2
1 3
2 4
2 5
8
1 2
8 7
1 3
8 6
1 4
8 5
1 8

Tuloste

12
94

Huomautus

Ensimmäisessä testitapauksessa on 17 erilaista alipuuta. 5 alipuista sisältää vain yhden solmun, joten niille $f(T') = 0$. Kaikki muut alipuut toteuttavat ehdon $f(T') = 1$. Siispä vastaus on 12.