Poniżej przedstawiono definicje poddrzewa i średnicy, które różnią się od standardowych w tym zadaniu.

Oto kilka definicji:

• Rozmiar drzewa $T$ to liczba jego wierzchołków, tj. $|V(T)|$.
• Stopień wierzchołka $i$ w drzewie $T$ to liczba krawędzi z nim incydentnych, oznaczany przez $deg_i$.
• Drzewo $T'$ jest poddrzewem drzewa $T$ wtedy i tylko wtedy, gdy spełnione są następujące warunki:
  • Dla każdego wierzchołka $v \in V(T')$, $v \in V(T)$.
  • Dla każdej krawędzi $e \in E(T')$, $e \in E(T)$.
• Niech $S_T$ będzie zbiorem wszystkich poddrzew drzewa $T$.
• Średnica drzewa $T$ to największy rozmiar spośród poddrzew $T$ spełniających $max(deg_i) \le 2$ w tym poddrzewie.
• Niech $R_k$ będzie zbiorem wszystkich maksymalnych drzew spełniających następujące warunki:
  • $max(deg_i) \le 3$.
  • Średnica drzewa wynosi $2k$.
• Dla drzewa $T$ definiujemy $f(T)$ jako największą liczbę całkowitą $k$ taką, że $S_T \cap R_k \neq \emptyset$. Jeśli taka $k$ nie istnieje, to $f(T)=0$.

Dane jest drzewo $T$ o $n$ wierzchołkach. Oblicz sumę wartości $f(T')$ po wszystkich poddrzewach $T'$ drzewa $T$, modulo $998244353$.

Dwa poddrzewa są uważane za różne, jeśli różnią się zbiorem wierzchołków lub zbiorem krawędzi.

Wejście

Każdy przypadek testowy zawiera wiele zestawów. Pierwszy wiersz zawiera liczbę całkowitą $t$ ($1 \le t \le 5 \times 10^4$) oznaczającą liczbę zestawów. Następnie następują opisy zestawów.

W każdym zestawie pierwszy wiersz zawiera liczbę całkowitą $n$ ($1 \le n \le 10^5$, $\sum n \le 10^6$) oznaczającą liczbę wierzchołków drzewa $T$.

Kolejne $n-1$ wierszy zawiera po dwie liczby całkowite $u, v$ ($1 \le u \neq v \le n$) oznaczające krawędzie drzewa $T$.

Wyjście

Dla każdego zestawu wypisz liczbę całkowitą będącą resztą z dzielenia sumy wartości $f(T')$ przez $998244353$.

Przykład

Wejście 1

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

Wyjście 1

12
94

Uwagi

W pierwszym zestawie istnieje 17 różnych poddrzew. Spośród nich 5 poddrzew zawiera tylko jeden wierzchołek, więc $f(T') = 0$. Wszystkie pozostałe poddrzewa spełniają $f(T') = 1$. Stąd odpowiedź wynosi 12.