Dưới đây là định nghĩa bất thường về cây con và đường kính trong bài toán này. Dưới đây là một số định nghĩa: Kích thước của một cây $T$ là số đỉnh trong nó, tức là $|V(T)|$. Bậc của một đỉnh $i$ trong cây $T$ là số cạnh nối với nó, ký hiệu là $deg_i$. Một cây $T'$ là cây con của cây $T$ nếu và chỉ nếu: Với mọi đỉnh $v \in V(T')$, ta có $v \in V(T)$. Với mọi cạnh $e \in E(T')$, ta có $e \in E(T)$. Đặt $S_T$ là tập hợp các cây con của $T$. Đường kính của một cây $T$ là kích thước của cây con lớn nhất của $T$ sao cho $max(deg_i) \le 2$ trong cây con đó. Đặt $R_k$ là tập hợp các cây lớn nhất sao cho: $max(deg_i) \le 3$. Đường kính của cây là $2k$. * Với một cây $T$, đặt $f(T)$ là số nguyên $k$ lớn nhất sao cho $S_T \cap R_k \neq \emptyset$. Nếu không có số $k$ nào như vậy, $f(T) = 0$.

Bạn được cho một cây $T$ có $n$ đỉnh. Đếm tổng của $f(T')$ cho tất cả các cây con $T'$ của $T$ theo modulo $998244353$. Hai cây con được coi là khác nhau nếu chúng có tập đỉnh hoặc tập cạnh khác nhau.

Dữ liệu vào

Mỗi bài kiểm tra chứa nhiều trường hợp. Dòng đầu tiên chứa một số nguyên $t$ ($1 \le t \le 5 \times 10^4$), chỉ số lượng trường hợp kiểm tra. Mô tả các trường hợp kiểm tra theo sau. Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 10^5$, $\sum n \le 10^6$), chỉ số lượng đỉnh của cây $T$. $n-1$ dòng tiếp theo chứa hai số nguyên $u, v$ ($1 \le u \neq v \le n$), chỉ một cạnh trên cây $T$.

Dữ liệu ra

Với mỗi trường hợp kiểm tra, in ra một số nguyên, chỉ tổng của $f(T')$, theo modulo $998244353$.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

12
94

Ghi chú

Đối với trường hợp kiểm tra đầu tiên, có 17 cây con khác nhau. 5 trong số các cây con chỉ chứa một đỉnh và do đó $f(T') = 0$. Tất cả các cây con còn lại thỏa mãn $f(T') = 1$. Do đó, câu trả lời là 12.