题目描述

给定一棵节点数为 $n$ 的树，需要删除若干条边，使得剩余部分每个连通块的节点数均为 $k$ 或者 $k+1$。求有多少种不同的方案满足上述条件，对 $998244353$ 取模。

两种方案被认为是不同的，当且仅当一条边在其中一种方案中被删除，而在另一种方案中没有被删除。

输入格式

本题有多组数据。第一行输入一个整数 $T$ 表示数据组数，对于每组数据：

第一行输入两个整数 $n,k$。

接下来的 $n-1$ 行，第 $i$ 行输入两个整数 $u_i,v_i$ 表示第 $i$ 条边连接了节点 $u_i,v_i$。

输出格式

每组数据输出一行一个整数，表示答案对 $998244353$ 取模的值。

输入样例

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

输出样例

2
1

说明提示

输入样例 #2

1
2 1
1 2

输出样例 #2

2

输入样例 #3

1
3 1
1 2
2 3

输出样例 #3

3

数据范围

对于 $10\%$ 的数据，有 $T=1,n=20$。

对于 $50\%$ 的数据，有 $\sum n\leq 5000$。

对于另外 $10\%$ 的数据，树是一条链。

对于 $100\%$ 的数据，$2\leq n\leq 10^5,1\leq k\leq n, \sum n\leq 3\times 10^5$。