問題「Cut Cut Cut!」を無事に解き終えたLittle Cyan Fishは、グラフ内の連結成分を分割するスキルをさらに磨こうとしている。

ある日、Little Cyan Fishは謎の賢者からユニークな問題を出題された。彼は、$n$ 個の頂点を持つ根のない木と、整数 $k$ を与えられる。$E$ をその木のすべての辺の集合とする。Little Cyan Fishの目的は、部分集合 $E' \subseteq E$ を特定することである。$E'$ に含まれるすべての辺を取り除くと、グラフはいくつかの連結成分に分割され、それぞれのサイズは $k$ または $(k + 1)$ となる。

分割の専門家であるLittle Cyan Fishは、この問題を巧みに解く。しかし、謎の賢者の好奇心は単なる習熟の域を超えていた。賢者はすべての潜在的な結果を探求しようとしている。その結果、賢者はLittle Cyan Fishに対し、指定された条件を満たしながら $E' \subseteq E$ を選択するすべての異なる方法の総数を求める課題を与えた。選択された辺の部分集合が異なれば、2つの方法は異なるとみなされる。

Little Cyan Fishがこの課題を達成できるよう手助けしてほしい。答えは非常に大きくなる可能性があるため、998 244 353 で割った余りを求める必要がある。

入力

入力には複数のテストケースが含まれる。入力の最初の行には、テストケースの数を示す整数 $T$ が含まれる。各テストケースについて：

最初の行には、木に含まれる頂点の数と、より小さい連結成分の目標サイズを示す2つの整数 $n$ と $k$ ($2 \le n \le 10^5, 1 \le k \le n$) が含まれる。

続く $(n - 1)$ 行には、木における頂点 $u_i$ と $v_i$ を結ぶ辺を示す2つの整数 $u_i$ と $v_i$ ($1 \le u_i, v_i \le n$) が含まれる。

すべてのテストケースにおける $n$ の合計は $3 \times 10^5$ を超えないことが保証されている。

出力

各テストケースについて、条件を満たすように辺の部分集合 $E'$ を選択する方法の総数を 998 244 353 で割った余りを1行に出力せよ。

入出力例

入力 1

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

出力 1

2
1

注記

$(u, v)$ を頂点 $u$ と $v$ を結ぶ辺とする。最初のサンプルテストケースにおいて、有効な辺の部分集合は $\{(2, 4), (3, 5)\}$ と $\{(1, 2), (3, 5)\}$ の2つである。