以下は、この問題における部分木と直径の通常とは異なる定義です。

以下にいくつかの定義を示します。

• 木 $T$ のサイズとは、その頂点数、すなわち $|V(T)|$ である。
• 木 $T$ における頂点 $i$ の次数とは、それに接続する辺の数であり、$deg_i$ で表す。
• 木 $T'$ が木 $T$ の部分木であるとは、以下の条件を満たすことと同値である：
  • すべての頂点 $v \in V(T')$ に対し、$v \in V(T)$ である。
  • すべての辺 $e \in E(T')$ に対し、$e \in E(T)$ である。
• $S_T$ を $T$ の部分木全体の集合とする。
• 木 $T$ の直径とは、$T$ の部分木であって、その部分木における $max(deg_i) \le 2$ を満たすもののうち、最大のサイズである。
• $R_k$ を以下の条件を満たす最大の木全体の集合とする：
  • $max(deg_i) \le 3$ である。
  • 木の直径は $2k$ である。
• 木 $T$ に対し、$f(T)$ を、$S_T \cap R_k \neq \emptyset$ となる最大の整数 $k$ と定義する。そのような $k$ が存在しない場合、$f(T)=0$ とする。

あなたは $n$ 頂点からなる木 $T$ を与えられる。$T$ のすべての部分木 $T'$ に対する $f(T')$ の総和を $998244353$ で割った余りを求めよ。 二つの部分木は、頂点集合または辺集合が異なる場合に異なるものとみなす。

入力

各テストケースは複数のケースを含む。最初の行には整数 $t$ ($1 \le t \le 5 \times 10^4$) が含まれ、テストケースの数を示す。続いてテストケースの説明が続く。 各テストケースの最初の行には整数 $n$ ($1 \le n \le 10^5$, $\sum n \le 10^6$) が含まれ、木 $T$ の頂点数を示す。 続く $n-1$ 行にはそれぞれ二つの整数 $u, v$ ($1 \le u \neq v \le n$) が含まれ、木 $T$ の辺を示す。

出力

各テストケースについて、$f(T')$ の総和を $998244353$ で割った余りを表す整数を出力せよ。

入出力例

入力 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

出力 1

12
94

注記

最初のテストケースでは、異なる部分木は 17 個ある。そのうち 5 個の部分木は頂点を 1 つだけ含み、したがって $f(T') = 0$ である。残りのすべての部分木は $f(T') = 1$ を満たす。したがって、答えは 12 となる。