你是一名舰长，你的战舰由 $n$ 个舱室组成，并另有 $n-1$ 条通道，每条通道连接一对舱室；通过若干通道，任意一对舱室都互相可达（可以将战舰看作一棵树）。

在战斗中，由于海浪汹涌，船体颠簸，你和你的敌人都只能大致地瞄准对方：每当你的战舰被击中时，一条未被打断的通道将被打断，且可以认为每条未被打断的通道之间被（选中）打断的概率相等。

一艘战舰的战斗力为所有“由未被打断的通道连接成的舱室连通块大小（所含舱室数）的平方”之和。

为了更好地分析局势，请计算当战舰共计被击中 $0 \sim k$ 次时，战舰的期望战斗力――被击中大于 $k$ 次时考虑战舰的战斗力似乎没有什么必要……

输入格式

第一行含一个正整数 $t$ $(1 \leq t \leq 500)$，表示共有多少组询问;

接下来 $t$ 组询问:

第一行含三个整数：用于在视觉上分割询问的一个数 $sp=25500$，战舰的舱室数 $n$ $(1 \leq n \leq 2 \times 10^5)$，和参数 $k$ $(0 \leq k \leq \min(n-1,100))$；

接下来 $n-1$ 行，第 $i$ 行含两个正整数 $u_i$ 和 $v_i$ $(1 \leq u_i,v_i \leq n, u_i \neq v_i)$，表示第 $i$ 条通道所连两舱室的编号。

保证 $\sum n \leq 10^6$。

输出格式

对每组询问，输出一行 $k+1$ 个非负整数，第 $i$ 个数代表“战舰共计被击中 $i-1$ 次”时战舰的期望战斗力对 $998244353$ 取模后的结果。

样例

输入

2
25500 3 2
1 2
1 3
25500 7 5
2 5
7 1
4 5
4 7
5 6
3 7

输出

9 5 3
49 33 532397011 598946628 133099259 9

提示

询问2的各答案真实值依次为 $49,33,34115,815,17915,9$。