作为 Chtholly 学院的一员，你想要赶往战场去帮助 Chtholly。 天空中共有 $n$ 座岛屿，你位于第一座岛屿上。 起初，岛屿之间有 $n-1$ 条运输线路，每条线路连接两座岛屿。这些线路保证了天空中任意两座岛屿之间都是可达的。 然而，由于地面野兽的持续攻击，每一条运输线路都有 $50\%$ 的概率被摧毁。 你想要知道，当我们考虑所有 $2^{n-1}$ 种可能的现实情况（每条运输线路可能被摧毁或未被摧毁，从而产生两种分支现实）时，有多少种现实情况能让你恰好到达 $k$ 座岛屿（包括第一座岛屿）。 答案可能很大，你只需要输出答案对 $1811939329$ 取模的结果。

输入格式

输入包含多组测试数据，第一行包含一个整数 $T$ ($1 \le T \le 18$)，表示测试数据的组数。 对于每组测试数据，第一行包含一个整数 $n$ ($1 \le n \le 100000$)，表示天空中的岛屿数量。接下来的 $n-1$ 行，每行包含两个整数 $x$ 和 $y$ ($1 \le x, y \le n$)，描述了第 $x$ 座岛屿和第 $y$ 座岛屿之间的一条边。 约一半的测试数据满足 $1 \le n \le 5000$。

输出格式

对于每组测试数据，输出一行，包含 $n$ 个数字。 第 $k$ 个数字表示你能恰好到达 $k$ 座岛屿的可能现实情况的数量。

样例

样例输入 1

1
5
1 2
2 3
3 4
4 5

样例输出 1

8 4 2 1 1