黑猫的世界正在崩溃。
在这个世界中,它可以表示为一棵有根树,根位于节点 $$$1$$$,Liki 和 Sasami 需要揭开世界的真相。
每天,他们都可以探索尚未崩溃的节点$$$u$$$。经过这次探索,黑猫导致 $$$u$$$ 及其子树中的所有节点崩溃。另外,在第$$$i$$$天结束时,如果存在,则$$$n-i+1$$$节点也会崩溃。
对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,确定 Liki 和 Sasami 精确探索 $$$i$$$ 天的探索方案数量(即,他们精确执行 $$$i$$$ 操作),最后一次探索位于节点 $$$1$$$。结果应以 $$$998\,244\,353$$$ 为模进行计算。
注意: 保证节点 $$$1$$$ 到 $$$n$$$ 可以形成树的“DFS”顺序,这意味着存在深度优先搜索遍历,其中第 $$$i$$$ 访问的节点是 $$$i$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行恰好包含一个数字 $$$n$$$ ($$$3 \le n \le 80$$$)。
以下 $$$n - 1$$$ 行中的每一行都包含两个整数 $$$u_i$$$ 和 $$$v_i$$$,表示由边连接的两个顶点 ($$$1 \le u_i, v_i \le n$$$)。保证给定的边形成一棵树。还保证了顶点能够形成“DFS”遍历顺序。
保证所有测试用例的$$$n$$$总和不超过$$$80$$$
输出
对于每个测试用例,打印 $$$n$$$ 整数,其中第 $$$i$$$ 整数表示恰好 $$$i$$$ 天的探索方案数量,以 $$$998\,244\,353$$$ 为模。
示例
输入复制
241 22 32 474 26 15 17 62 31 2
输出复制
1 3 3 1 1 6 23 48 43 17 1
注意
对于第一个测试用例,以下操作序列是合法的:
$$$\{1\},\{2,1\},\{3,1\},\{4,1\},\{3,2,1\},\{4,2,1\},\{4,3,1\},\{4,3,2,1\}$$$.