E. Alice's Adventures in the Rabbit Hole
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice is at the bottom of the rabbit hole! The rabbit hole can be modeled as a tree$$$^{\text{∗}}$$$ which has an exit at vertex $$$1$$$, and Alice starts at some vertex $$$v$$$. She wants to get out of the hole, but unfortunately, the Queen of Hearts has ordered her execution.

Each minute, a fair coin is flipped. If it lands heads, Alice gets to move to an adjacent vertex of her current location, and otherwise, the Queen of Hearts gets to pull Alice to an adjacent vertex of the Queen's choosing. If Alice ever ends up on any of the non-root leaves$$$^{\text{†}}$$$ of the tree, Alice loses.

Assuming both of them move optimally, compute the probability that Alice manages to escape for every single starting vertex $$$1\le v\le n$$$. Since these probabilities can be very small, output them modulo $$$998\,244\,353$$$.

Formally, let $$$M = 998\,244\,353$$$. It can be shown that the exact answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

$$$^{\text{∗}}$$$A tree is a connected simple graph which has $$$n$$$ vertices and $$$n-1$$$ edges.

$$$^{\text{†}}$$$A leaf is a vertex that is connected to exactly one edge.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — the number of vertices in the tree.

The $$$i$$$-th of the next $$$n - 1$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$ and $$$x_i \neq y_i$$$) — the edges of the tree. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output $$$n$$$ integers on one line — the probabilities of Alice escaping starting from vertex $$$1, 2, \ldots, n$$$. Since these probabilities can be very small, output them modulo $$$998\,244\,353$$$.

Example
Input
2
5
1 2
1 3
2 4
3 5
9
1 2
2 3
4 5
5 6
7 8
8 9
2 4
5 7
Output
1 499122177 499122177 0 0 
1 499122177 0 332748118 166374059 0 443664157 720954255 0
Note

For the first test case:

  1. Alice escapes from the root (vertex $$$1$$$) by definition with probability $$$1$$$.
  2. Alice immediately loses from vertices $$$4$$$ and $$$5$$$ since they are leaves.
  3. From the other two vertices, Alice escapes with probability $$$\frac 12$$$ since the Queen will pull her to the leaves.