Problem Statement

You are given a tree with $N$ vertices numbered $1$ to $N$. Here, $N$ is at least $2$. The $i$-th edge $(1\le i\le N-1)$ connects vertices $u_i$ and $v_i$.

Perform the following operation on this tree exactly $K$ times. The $k$-th operation $(1\le k\le K)$ is as follows.

• Choose one of the $N-2+k$ edges of the tree at that point uniformly at random. Let $u$ and $v$ be the vertices connected by the chosen edge. Prepare a new vertex $N+k$, add edges connecting vertices $u$ and $N+k$ and connecting vertices $v$ and $N+k$, then delete the chosen edge.

Note that for $k=1,2,\ldots,K$, the tree will have $N+k$ vertices after the $k$-th operation.

Find the expected value, modulo $998244353$, of $\displaystyle \sum_{1\le i < j\le N+K} \text{dist}(i,j)$ after $K$ operations. Here, $\text{dist}(i,j)$ denotes the distance between vertices $i$ and $j$ in the tree.

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

Definition of expected value $\ \text{mod}\ 998244353$ It can be proved that the expected value to be found is always a rational number. Moreover, under the constraints of this problem, when this rational number is expressed as an irreducible fraction $\displaystyle \frac{P}{Q}$, it can be proved that $Q \neq 0 \bmod 998244353$. Thus, there is a unique integer $R$ satisfying $R \times Q \equiv P \bmod 998244353, 0 \leq R \lt 998244353$. Find this $R$.

Constraints

• $1\le T$
• $2\le N$
• The sum of $N$ over all test cases is at most $3\times 10^5$.
• $1\le K$
• The sum of $K$ over all test cases is at most $10^6$.
• $1\le u_i < v_i \le N$
• The given graph is a tree.
• All input values are integers.

Input

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

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

Each test case is given in the following format:

N K
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

Output

Output the answers for the test cases in order, separated by newlines.