CF1554E.You

You are given a tree with $n$ nodes. As a reminder, a tree is a connected undirected graph without cycles.

Let $a_1, a_2, \ldots, a_n$ be a sequence of integers. Perform the following operation exactly $n$ times:

• Select an unerased node $u$. Assign $a_u :=$ number of unerased nodes adjacent to $u$. Then, erase the node $u$ along with all edges that have it as an endpoint.

For each integer $k$ from $1$ to $n$, find the number, modulo $998\,244\,353$, of different sequences $a_1, a_2, \ldots, a_n$ that satisfy the following conditions:

• it is possible to obtain $a$ by performing the aforementioned operations exactly $n$ times in some order.
• $\operatorname{gcd}(a_1, a_2, \ldots, a_n) = k$. Here, $\operatorname{gcd}$ means the greatest common divisor of the elements in $a$.

给你一棵包含 $n$ 个节点的树。需要提醒的是，树是一种无环的连通无向图。

设 $a_1, a_2, \ldots, a_n$ 是一个整数序列。执行以下操作恰好 $n$ 次：

• 选择一个尚未被擦除的节点 $u$。令 $a_u :=$ 与 $u$ 相邻且尚未被擦除的节点的数量。然后，将节点 $u$ 及其所有以 $u$ 为端点的边一并擦除。

对每个从 $1$ 到 $n$ 的整数 $k$，求满足以下条件的不同序列 $a_1, a_2, \ldots, a_n$ 的个数（对 $998\,244\,353$ 取模）：

• 存在某种执行上述操作 $n$ 次的顺序，使得最终得到的序列为 $a$；
• $\operatorname{gcd}(a_1, a_2, \ldots, a_n) = k$。此处 $\operatorname{gcd}$ 表示序列 $a$ 中所有元素的最大公约数。

The first line contains a single integer $t$ ($1 \le t \le 10\,000$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 10^5$).

Each of the next $n - 1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n$) indicating there is an edge between vertices $u$ and $v$. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $3 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10\,000$）—— 表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^5$）。

接下来的 $n - 1$ 行中，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$），表示顶点 $u$ 与顶点 $v$ 之间存在一条边。保证所给的边构成一棵树。

保证所有测试用例的 $n$ 之和不超过 $3 \cdot 10^5$。

For each test case, print $n$ integers in a single line, where for each $k$ from $1$ to $n$, the $k$-th integer denotes the answer when $\operatorname{gcd}$ equals to $k$.

对于每个测试用例，在一行中输出 $n$ 个整数，其中对每个从 $1$ 到 $n$ 的 $k$，第 $k$ 个整数表示当 $\operatorname{gcd}$ 等于 $k$ 时的答案。

In the first test case,

• If we delete the nodes in order $1 \rightarrow 2 \rightarrow 3$ or $1 \rightarrow 3 \rightarrow 2$, then the obtained sequence will be $a = [2, 0, 0]$ which has $\operatorname{gcd}$ equals to $2$.
• If we delete the nodes in order $2 \rightarrow 1 \rightarrow 3$, then the obtained sequence will be $a = [1, 1, 0]$ which has $\operatorname{gcd}$ equals to $1$.
• If we delete the nodes in order $3 \rightarrow 1 \rightarrow 2$, then the obtained sequence will be $a = [1, 0, 1]$ which has $\operatorname{gcd}$ equals to $1$.
• If we delete the nodes in order $2 \rightarrow 3 \rightarrow 1$ or $3 \rightarrow 2 \rightarrow 1$, then the obtained sequence will be $a = [0, 1, 1]$ which has $\operatorname{gcd}$ equals to $1$.

Note that here we are counting the number of different sequences, not the number of different orders of deleting nodes.

在第一个测试用例中，

• 如果我们按顺序 $1 \rightarrow 2 \rightarrow 3$ 或 $1 \rightarrow 3 \rightarrow 2$ 删除节点，则得到的序列为 $a = [2, 0, 0]$，其 $\operatorname{gcd}$ 等于 $2$。
• 如果我们按顺序 $2 \rightarrow 1 \rightarrow 3$ 删除节点，则得到的序列为 $a = [1, 1, 0]$，其 $\operatorname{gcd}$ 等于 $1$。
• 如果我们按顺序 $3 \rightarrow 1 \rightarrow 2$ 删除节点，则得到的序列为 $a = [1, 0, 1]$，其 $\operatorname{gcd}$ 等于 $1$。
• 如果我们按顺序 $2 \rightarrow 3 \rightarrow 1$ 或 $3 \rightarrow 2 \rightarrow 1$ 删除节点，则得到的序列为 $a = [0, 1, 1]$，其 $\operatorname{gcd}$ 等于 $1$。

注意：此处我们统计的是不同序列的数量，而非不同删除节点顺序的数量。