Problem Statement

You are given a tree with $N$ vertices numbered $1$ to $N$. The $i$-th edge of the tree connects vertices $u_i$ and $v_i$.

For each $K=1, 2, \ldots, N$, solve the following problem:

There are $K$ stones numbered $1, 2, \ldots, K$, with the stone numbered $i$ placed on vertex $i$. You can repeatedly perform the following operation:

• Choose two vertices $u$ and $v$ connected by an edge such that $u$ has a stone on it and $v$ does not. Move the stone from $u$ to $v$.

Find the number, modulo $998244353$, of possible configurations of the stones after performing the operations. Two configurations are distinguished if and only if there is a stone whose position differs between those configurations.

$T$ test cases are given; solve each of them.

Constraints

• $1\leq T\leq 10^5$
• $1\leq N\leq 2\times 10^5$
• $1\leq u_i, v_i\leq N$
• The given graph is a tree.
• The sum of $N$ over all test cases in a single input is at most $2\times 10^5$.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\vdots
\text{case}_T

Each test case is given in the following format:

N
u_1 v_1
\vdots
u_{N-1} v_{N-1}

Output

Print $T$ lines. The $i$-th line should contain the answers for $K=1, 2, \ldots, N$ for the $i$-th test case, separated by spaces.