Merk den uvanlige definisjonen av undertre og diameter i denne oppgaven.

Her er noen definisjoner:

• Størrelsen på et tre $T$ er antall noder i det, det vil si $|V(T)|$.
• Graden til en node $i$ i treet $T$ er antall kanter som er koblet til den, betegnet med $\operatorname{deg}_i$.
• Et tre $T'$ er et undertre av treet $T$ hvis og bare hvis:
  • For alle noder $v \in V(T')$ gjelder $v \in V(T)$.
  • For alle kanter $e \in E(T')$ gjelder $e \in E(T)$.
• La $S_T$ være mengden av undertrær av $T$.
• Diameteren til et tre $T$ er størrelsen på det største undertreet av $T$ slik at $\max(\operatorname{deg}_i) \le 2$ i undertreet.
• La $R_x$ være mengden av de største trærne slik at:
  • $\max(\operatorname{deg}_i) \le 3$.
  • Diameteren til treet er $2x$.
• For et tre $T$, la $f(T)$ være det største $k$ slik at $S_T \cap R_k \ne \emptyset$. Hvis det ikke finnes noen slik $k$, er $f(T) = 0$.

Du får et tre $T$ med $n$ noder. Regn ut summen av $f(T')$ for alle undertrær $T'$ av $T$ modulo $998244353$. To undertrær er forskjellige hvis og bare hvis de har forskjellig nodemengde eller kantmengde.

Inndata

Hver test inneholder flere testtilfeller. Den første linjen inneholder ett heltall $t$ ($1 \le t \le 5 \times 10^4$), som angir antall testtilfeller. Beskrivelsen av testtilfellene følger.

Den første linjen inneholder ett heltall $n$ ($1 \le n \le 10^5$, $\sum n \le 10^6$), som angir antall noder i treet $T$.

Hver av de følgende $n - 1$ linjene inneholder to heltall $u, v$ ($1 \le u \ne v \le n$), som angir en kant i treet $T$.

Utdata

For hvert testtilfelle, skriv ut ett heltall som angir summen av $f(T')$, modulo $998244353$.

Eksempel

Inndata

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

Utdata

12
94

Forklaring

For det første testtilfellet er det 17 forskjellige undertrær. 5 av undertrærne inneholder bare én node, og dermed er $f(T') = 0$. Alle de andre undertrærne oppfyller $f(T') = 1$. Dermed er svaret 12.