Migrated from Lutece 3224 删删乐

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给定一棵 $n$ 个点的树。

现执行以下操作 $n$ 次：

1. 任选一个未被删除的点 $u$，令 $a_u$ 等于与 $u$ 相连且未被删除的边的条数。
2. 将点 $u$ 及与 $u$ 相连的所有边删除。

对于每个 $k\in[1,n]$， 求最终能得到多少个不同的序列 $\{a\}$，满足 $\gcd(a_1,a_2,\dots,a_n)=k$。答案对 $998244353$ 取模。

对任意自然数 $x$ ，规定 $\gcd(x,0)=x$

Input

第一行，一个正整数 $T$，表示数据组数。

对于每组测试数据，第一行，一个正整数 $n$。

接下来 $n-1$ 行，每行两个正整数，描述一条边 $u\leftrightarrow v$ 。

Output

对于每组测试数据，输出一行，$n$ 个正整数，用空格间隔，第 $i$ 个数表示当 $k=i$ 时的答案。

Samples

1
3
1 2
1 3

3 1 0

Constraints

$2\leq n \leq 10^5$

$T\leq 10,\sum n\leq 10^5$

Resources

2024 UESTC ICPC Training for Math