Beachte die ungewöhnliche Definition von Teilbaum und Durchmesser in diesem Problem.

Hier sind einige Definitionen:

• Die Größe eines Baums $T$ ist die Anzahl seiner Knoten, also $|V(T)|$.
• Der Grad eines Knotens $i$ im Baum $T$ ist die Anzahl der mit ihm verbundenen Kanten, bezeichnet mit $\operatorname{deg}_i$.
• Ein Baum $T'$ ist genau dann ein Teilbaum des Baums $T$, wenn Folgendes gilt:
  • Für alle Knoten $v \in V(T')$ gilt $v \in V(T)$.
  • Für alle Kanten $e \in E(T')$ gilt $e \in E(T)$.
• Sei $S_T$ die Menge der Teilbäume von $T$.
• Der Durchmesser eines Baums $T$ ist die Größe des größten Teilbaums von $T$, sodass im Teilbaum $\max(\operatorname{deg}_i) \le 2$ gilt.
• Sei $R_x$ die Menge der größten Bäume, sodass Folgendes gilt:
  • $\max(\operatorname{deg}_i) \le 3$.
  • Der Durchmesser des Baums ist $2x$.
• Für einen Baum $T$ sei $f(T)$ das größte $k$, sodass $S_T \cap R_k \ne \emptyset$ gilt. Wenn es kein solches $k$ gibt, ist $f(T) = 0$.

Gegeben ist ein Baum $T$ mit $n$ Knoten. Berechne die Summe von $f(T')$ über alle Teilbäume $T'$ von $T$ modulo $998244353$. Zwei Teilbäume sind genau dann verschieden, wenn sie unterschiedliche Knotenmengen oder Kantenmengen haben.

Eingabe

Jeder Test enthält mehrere Testfälle. Die erste Zeile enthält eine ganze Zahl $t$ ($1 \le t \le 5 \times 10^4$), die die Anzahl der Testfälle angibt. Es folgt die Beschreibung der Testfälle.

Die erste Zeile enthält eine ganze Zahl $n$ ($1 \le n \le 10^5$, $\sum n \le 10^6$), die die Anzahl der Knoten im Baum $T$ angibt.

Jede der folgenden $n - 1$ Zeilen enthält zwei ganze Zahlen $u, v$ ($1 \le u \ne v \le n$), die eine Kante im Baum $T$ angeben.

Ausgabe

Gib für jeden Testfall eine ganze Zahl aus, die die Summe von $f(T')$ modulo $998244353$ angibt.

Beispiel

Eingabe

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

Ausgabe

12
94

Hinweis

Für den ersten Testfall gibt es 17 verschiedene Teilbäume. 5 der Teilbäume enthalten nur einen Knoten und somit gilt dort $f(T') = 0$. Alle anderen Teilbäume erfüllen $f(T') = 1$. Daher lautet die Antwort 12.