Rikka with Match

Time Limit: 13000/6500 MS (Java/Others)

Memory Limit: 262144/262144 K (Java/Others)


As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

Yuta has an undirected connected graph $G=\langle V,E \rangle$ with $n$ nodes and $n-1$ edges. Yuta can choose some edges in $E$ and remove them. It is clear that Yuta has $2^{n-1}$ different ways to remove.

Now, Yuta want to know the number of ways to remove the edges which make the maximum matching size of the remaining graph $G’$ is divisible by $m$.

It is too difficult for Rikka. Can you help her?  

An edge set $S$ is a match of $G=\langle V,E \rangle$ if and only if each nodes in $V$ connects to at most one edge in $S$. The maximum matching of graph $G$ is defined as the match of $G$ with the largest size.


The first line contains a number $t(1 \leq t \leq 100)$, the number of the testcases. And there are no more than $3$ testcases with $n > 1000$.

For each testcase, the first line contains two numbers $n,m(1 \leq n \leq 5 \times 10^4,1 \leq m \leq 200)$.

Then $n-1$ lines follow, each line contains two numbers $u,v$ which describes an edge in $G$.


For each testcase, print a single line with a single number -- the answer modulo $998244353$.

Sample Input

1 4 2 1 2 2 3 3 4

Sample Output





2017 Multi-University Training Contest - Te