Observera den ovanliga definitionen av delträd och diameter i detta problem.

Här är några definitioner:

• Storleken på ett träd $T$ är antalet hörn i det, det vill säga $|V(T)|$.
• Graden för ett hörn $i$ i trädet $T$ är antalet kanter som är anslutna till det, betecknat med $\operatorname{deg}_i$.
• Ett träd $T'$ är ett delträd till trädet $T$ om och endast om:
  • För alla hörn $v \in V(T')$ gäller $v \in V(T)$.
  • För alla kanter $e \in E(T')$ gäller $e \in E(T)$.
• Låt $S_T$ vara mängden av delträd till $T$.
• Diametern för ett träd $T$ är storleken på det största delträdet till $T$ sådant att $\max(\operatorname{deg}_i) \le 2$ i delträdet.
• Låt $R_x$ vara mängden av de största träden sådana att:
  • $\max(\operatorname{deg}_i) \le 3$.
  • Trädets diameter är $2x$.
• För ett träd $T$, låt $f(T)$ vara det största $k$ sådant att $S_T \cap R_k \ne \emptyset$. Om det inte finns något sådant $k$ är $f(T) = 0$.

Du får ett träd $T$ med $n$ noder. Beräkna summan av $f(T')$ för alla delträd $T'$ till $T$ modulo $998244353$. Två delträd är olika om och endast om de har olika hörnmängd eller kantmängd.

Indata

Varje test innehåller flera testfall. Den första raden innehåller ett heltal $t$ ($1 \le t \le 5 \times 10^4$), som anger antalet testfall. Beskrivningen av testfallen följer.

Den första raden innehåller ett heltal $n$ ($1 \le n \le 10^5$, $\sum n \le 10^6$), som anger antalet hörn i trädet $T$.

Var och en av de följande $n - 1$ raderna innehåller två heltal $u, v$ ($1 \le u \ne v \le n$), som anger en kant i trädet $T$.

Utdata

För varje testfall, skriv ut ett heltal som anger summan av $f(T')$, modulo $998244353$.

Exempel

Indata

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

Förklaring

För det första testfallet finns det 17 olika delträd. 5 av delträden innehåller bara ett hörn och därmed är $f(T') = 0$. Alla övriga delträd uppfyller $f(T') = 1$. Alltså är svaret 12.