The world of the black cat is collapsing.

In this world, which can be represented as a rooted tree with root at node $$$1$$$, Liki and Sasami need to uncover the truth about the world.

Each day, they can explore a node $$$u$$$ that has not yet collapsed. After this exploration, the black cat causes $$$u$$$ and all nodes in its subtree to collapse. Additionally, at the end of the $$$i$$$ th day, if it exists, the number $$$n-i+1$$$ node will also collapse.

For each $$$i$$$ from $$$1$$$ to $$$n$$$, determine the number of exploration schemes where Liki and Sasami explore exactly $$$i$$$ days (i.e., they perform exactly $$$i$$$ operations), with the last exploration being at node $$$1$$$. The result should be computed modulo $$$998\,244\,353$$$.

Note: It is guaranteed that nodes $$$1$$$ to $$$n$$$ can form a "DFS" order of the tree, meaning there exists a depth-first search traversal where the $$$i$$$ th visited node is $$$i$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains exactly one number $$$n$$$ ($$$3 \le n \le 80$$$).

Each of the following $$$n - 1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$, representing two vertices connected by an edge ($$$1 \le u_i, v_i \le n$$$). It is guaranteed that the given edges form a tree. It is also guaranteed that the vertices can form a "DFS" traversal order.

It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$80$$$

Output

For each test case, print $$$n$$$ integers, where the $$$i$$$ th integer represents the number of exploration schemes for exactly $$$i$$$ days, modulo $$$998\,244\,353$$$.

Note

For the first test case, the following operation sequences are legal:

$$$\{1\},\{2,1\},\{3,1\},\{4,1\},\{3,2,1\},\{4,2,1\},\{4,3,1\},\{4,3,2,1\}$$$.

Black Cat Collapse

Examples