Given a tree with $n$ vertices, each vertex is a black node with a probability of $50\%$ and a white node with a probability of $50\%$.

Given a positive integer $m$, an edge set is chosen uniformly at random (i.e., each edge has a $50\%$ probability of being in the edge set). Let $x$ be the size of the edge set. If for every edge in the edge set, the number of black nodes on the two sides of the edge is different, the score is $m^x$; otherwise, the score is $0$.

You need to calculate the expected score.

There are multiple test cases.

Input

The first line contains a positive integer $t$, representing the number of test cases.

For each test case, the first line contains two positive integers $n$ and $m$. The next $n-1$ lines each contain two positive integers $u$ and $v$, representing an edge.

Output

For each test case, output a single integer representing the expected score $\times 2^{2n-1}$ modulo $998244353$.

Examples

Input 1

2
3 5
1 2
2 3
10 23333333
3 1
4 2
6 7
8 6
2 5
3 6
10 1
9 7
1 2

Output 1

158
167850015

Subtasks

For 10% of the data, $n \leq 10$.

For 20% of the data, $n \leq 20$.

For 30% of the data, $n \leq 200$.

For 40% of the data, $n \leq 1000$.

For 50% of the data, $n \leq 3000$.

For 60% of the data, $n \leq 10000$.

For 70% of the data, $n \leq 15000$.

For 100% of the data, $t \leq 5$, $2 \leq n \leq 20000$, $\sum n \leq 70000$, $1 \leq m < 998244353$, $1 \leq u,v \leq n$.