一棵具有 $$$n$$$ 节点的树以及最初为空的集合 $$$S$$$ 从天而降。对于这个不太可能发生的事件,您欣喜若狂,执行了以下 $$$n - 1$$$ 次:
- 令 $$$x$$$ 为具有最大索引的叶子。
- 将 $$$x$$$ 添加到 $$$S$$$ 中(请注意,如果 $$$x$$$ 已经在 $$$S$$$ 中,则不会发生任何变化)。
- 选择 $$$x$$$ 以外的任何叶子并将其从树中删除。
确定您可以制作的不同集合 $$$S$$$ 的数量。由于数字可能很大,因此输出它对 $$$998\,244\,353$$$ 取模。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 树的大小。
接下来是 $$$n - 1$$$ 行,每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u,v \le n, u \ne v$$$),它们描述由边连接的一对顶点。保证给定的图是一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
输出可以以 $$$998\,244\,353$$$ 为模获得的不同集合的数量。
示例
输入复制
621 255 15 35 45 277 67 45 71 62 43 51010 910 810 710 69 58 47 36 25 142 43 11 441 42 33 4
输出复制
1131311
注意
对于第一个测试用例,只有一个可能的顺序:$$$1$$$,使得集合 $$$\{2\}$$$
对于第三个测试用例,树如下所示:
您可以进行以下设置:
- $$$\{3, 6, 7\}$$$ 按顺序删除 $$$1, 2, 3, 4, 5, 6$$$
- $$$\{3, 4, 6, 7\}$$$ 按顺序删除 $$$2, 1, 3, 4, 5, 6$$$
- $$$\{3, 4, 5, 6, 7\}$$$ 按顺序删除 $$$2, 3, 1, 4, 5, 6$$$
可以证明这些是唯一可以获得的集合。