题目描述

在成功解决了《Cut Cut Cut！》这道题目之后，小青鱼想要进一步提高他在划分图的连通块方面的能力。

有一天，一位神秘的智者向小青鱼提出了一个问题。在这个问题中，小青鱼被给定了一棵由 $n$ 个节点组成的无根树，以及一个整数 $k$。设 $E$ 为树中所有边的集合，小青鱼的任务是找到一个子集 $E' \subseteq E$，使得在移除 $E'$ 中的所有边后，图被划分为若干个连通块，且每个连通块的大小均为 $k$ 或 $(k+1)$。

当然，作为一位分割事物的大师，小青鱼轻松地解决了这个问题。但是神秘智者的欲望远不止于此。智者不仅想要掌握事物，还想了解所有可能的结果。因此，他要求小青鱼计算出有多少种选择 $E' \subseteq E$ 的方法满足上述条件。两种方案被视为不同的，若它们选择的边的子集不相同。

请帮助小青鱼完成这一挑战。由于答案可能很大，您只需提供答案对 $998\,244\,353$ 取模后的结果。

输入格式

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

第一行输入两个整数 $n$ 和 $k$（$2 \le n \le 10^5$，$1 \le k \le n$）表示树的节点数量以及较小的连通块的目标大小。

对于接下来 $(n - 1)$ 行，第 $i$ 行输入两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$）表示一条连接节点 $u_i$ 与 $v_i$ 的边。

保证所有数据 $n$ 之和不超过 $3 \times 10^5$。

输出格式

每组数据输出一行一个整数，表示选择子集 $E'$ 的方案数对 $998\,244\,353$ 取模后的结果。

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

提示

令 $(u, v)$ 表示一条连接节点 $u$ 和 $v$ 的边。对于第一组样例数据，两个合法的边的子集为 $\{(2, 4), (3, 5)\}$ 和 $\{(1, 2), (3, 5)\}$。