Description

Given an unrooted tree with $n$ nodes, labeled $1 \sim n$. Define a heavy-light decomposition scheme as follows: First, designate a node as the root to obtain a rooted tree; For every non-leaf node in the tree, choose exactly one child as the heavy child, and classify the edge connecting this node to the heavy child as a heavy edge, while classifying edges to other children as light edges; At this point, all heavy edges in the tree and their endpoints form several maximal simple paths, and all nodes on each path form a heavy chain. Define the *length of a heavy chain as the number of nodes it contains. Specifically, a node not connected to any heavy edge forms a heavy chain of length 1 by itself.

Little B recalls that years ago, while studying heavy-light decomposition, he proposed a randomized chain decomposition algorithm, with the following procedure: First, designate node 1 as the root; For every non-leaf node, choose the heavy child bottom-up: for a non-leaf node $u$ ($1 \le u \le n$), suppose it has $k$ children $v_1, v_2, \dots, v_k$. After recursively determining the heavy children of all children, let the lengths of the heavy chains containing $v_1, v_2, \dots, v_k$ be $l_1, l_2, \dots, l_k$ respectively. Then $u$ will choose a child with a probability proportional to the length of the heavy chain, i.e., the probability of choosing $v_i$ ($1 \le i \le k$) as the heavy child is $\frac{l_i}{\sum_{j=1}^k l_j}$.

Little B knows that the time complexity of heavy-light decomposition is closely related to the number of light edges on the simple path from each node to the root. You need to help him calculate the sum of the expectations of the number of light edges on the simple path from node $x$ to the root node 1, for every node $x$ ($1 \le x \le n$), under the aforementioned randomized chain decomposition algorithm. Since the answer may be large, you only need to output the result modulo $998, 244, 353$.

The definition of expectation is as follows: Let the possible values of a random variable $X$ be $x_1, \dots, x_m$, where the probability of $X = x_i$ ($1 \le i \le m$) is $p_i \in [0, 1]$, and $\sum_{i=1}^m p_i = 1$, then the expectation of $X$ is $$E[X] = \sum_{i=1}^m p_i x_i$$

Input

Read data from the file recollector.in.

This problem contains multiple test cases. The first line contains two non-negative integers $c, t$, representing the test case ID and the number of test cases, respectively. $c = 0$ indicates that this test case is a sample.

The following lines contain the test cases. For each test case: The first line contains a positive integer $n$, representing the number of nodes. The $i+1$-th line ($1 \le i \le n-1$) contains two positive integers $u_i, v_i$, representing a tree edge connecting node $u_i$ and node $v_i$.

Output

Output to the file recollector.out.

For each test case, output a single non-negative integer on a new line, representing the sum of the expectations of the number of light edges on the simple path from all nodes to the root, modulo $998, 244, 353$.

Examples

Examples 1

Input:

1 0 2
2 5
1 2
1 3
2 4
2 5
7 8
1 2
1 3
2 4
2 5
2 6
5 7
3 8

Output:

665496238
549034400

Note

Explanation of Example 1

The sample contains two test cases. For the first test case: Node 2 will choose node 4 and node 5 as the heavy child with equal probability; Node 1 will choose node 2 and node 3 as the heavy child with probabilities $2/3$ and $1/3$ respectively. Therefore, The expectation of the number of light edges on the simple path from node 1 to the root is 0; The expectation of the number of light edges on the simple path from node 2 to the root is $(2/3) \cdot 0 + (1/3) \cdot 1 = 1/3$; The expectation of the number of light edges on the simple path from node 3 to the root is $(2/3) \cdot 1 + (1/3) \cdot 0 = 2/3$; The expectation of the number of light edges on the simple path from node 4 to the root is $(2/3) \cdot (1/2) \cdot 0 + (2/3) \cdot (1/2) \cdot 1 + (1/3) \cdot (1/2) \cdot 1 + (1/3) \cdot (1/2) \cdot 2 = 5/6$; * The expectation of the number of light edges on the simple path from node 5 to the root is $5/6$. Thus, the answer is $0 + 1/3 + 2/3 + 5/6 + 5/6 = 8/3 \equiv 665, 496, 238 \pmod{998, 244, 353}$.

Examples 2

See recollector/recollector2.in and recollector/recollector2.ans in the contestant directory. This sample satisfies the constraints of test cases $3 \sim 5$.

Examples 3

See recollector/recollector3.in and recollector/recollector3.ans in the contestant directory. This sample satisfies the constraints of test cases $6, 7$.

Examples 4

See recollector/recollector4.in and recollector/recollector4.ans in the contestant directory. This sample satisfies the constraints of test cases $8 \sim 10$.

Examples 5

See recollector/recollector5.in and recollector/recollector5.ans in the contestant directory. This sample satisfies the constraints of test cases $11, 12$.

Examples 6

See recollector/recollector6.in and recollector/recollector6.ans in the contestant directory. This sample satisfies the constraints of test cases $13 \sim 16$.

Examples 7

See recollector/recollector7.in and recollector/recollector7.ans in the contestant directory. This sample satisfies the constraints of test cases $17 \sim 25$.

Constraints

For all test cases: $1 \le t \le 5$; $1 \le n \le 5, 000$; * For all $1 \le i \le n-1$, $1 \le u_i, v_i \le n$, and $(u_1, v_1), \dots, (u_{n-1}, v_{n-1})$ form a tree.

Special Property A: For all $1 \le i \le n-1$, $u_i = i$ and $v_i = i+1$. Special Property B: For all $1 \le x \le n$, the number of nodes on the simple path from node 1 to node $x$ does not exceed 100.