Takið eftir óvenjulegri skilgreiningu á hluttré og þvermáli í þessu verkefni.

Hér eru nokkrar skilgreiningar:

• Stærð trés $T$ er fjöldi hnúta í því, þ.e. $|V(T)|$.
• Stig hnúts $i$ í tré $T$ er fjöldi leggja sem tengjast honum, táknað með $\operatorname{deg}_i$.
• Tré $T'$ er hluttré trés $T$ ef og aðeins ef:
  • Fyrir alla hnúta $v \in V(T')$ gildir $v \in V(T)$.
  • Fyrir alla leggi $e \in E(T')$ gildir $e \in E(T)$.
• Látum $S_T$ vera mengi hluttrjáa trésins $T$.
• Þvermál trés $T$ er stærð stærsta hluttrés $T$ þannig að $\max(\operatorname{deg}_i) \le 2$ í hluttrénu.
• Látum $R_x$ vera mengi stærstu trjáa þannig að:
  • $\max(\operatorname{deg}_i) \le 3$.
  • Þvermál trésins er $2x$.
• Fyrir tré $T$, látum $f(T)$ vera stærsta $k$ þannig að $S_T \cap R_k \ne \emptyset$. Ef ekkert slíkt $k$ er til, þá er $f(T) = 0$.

Þér er gefið tré $T$ með $n$ hnútum. Reiknaðu summu $f(T')$ fyrir öll hluttré $T'$ í $T$ módulo $998244353$. Tvö hluttré eru ólík ef og aðeins ef þau hafa ólíkt hnútamengi eða ólíkt leggjamengi.

Inntak

Hvert próf inniheldur mörg prófunartilfelli. Fyrsta línan inniheldur eina heiltölu $t$ ($1 \le t \le 5 \times 10^4$), sem gefur til kynna fjölda prófunartilfella. Lýsing á prófunartilfellunum fylgir.

Fyrsta línan inniheldur eina heiltölu $n$ ($1 \le n \le 10^5$, $\sum n \le 10^6$), sem gefur til kynna fjölda hnúta í trénu $T$.

Hver af næstu $n - 1$ línum inniheldur tvær heiltölur $u, v$ ($1 \le u \ne v \le n$), sem gefa til kynna legg í trénu $T$.

Úttak

Fyrir hvert prófunartilfelli skal prenta eina heiltölu sem gefur til kynna summu $f(T')$, módulo $998244353$.

Dæmi

Inntak

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

Úttak

12
94

Athugasemd

Í fyrsta prófunartilfellinu eru 17 ólík hluttré. 5 hluttrjánna innihalda aðeins einn hnút og því er $f(T') = 0$. Öll hin hluttrén uppfylla $f(T') = 1$. Því er svarið 12.