After successfully solving the problem Cut Cut Cut!, Little Cyan Fish seeks to further hone his skills in partitioning connected components within graphs.

One day, Little Cyan Fish is challenged by a mysterious sage with a unique problem. He is presented with an unrooted tree containing $n$ vertices and is given an integer $k$. Let $E$ represent the set of all edges in the tree. Little Cyan Fish’s objective is to identify a subset $E' \subseteq E$. Upon removing all edges in $E'$, the graph should split into several connected components, each with a size of either $k$ or $(k + 1)$.

As an expert in partitioning, Little Cyan Fish adeptly solves this problem. However, the mysterious sage’s curiosity extends beyond mere mastery. He seeks to explore all potential outcomes. Consequently, he tasks Little Cyan Fish with determining the total number of different ways to select $E' \subseteq E$ while adhering to the stated condition. Two ways are considered different if the selected subsets of edges are different.

Please help Little Cyan Fish to finish this challenge. As the answer may be large, you only need to provide the answer modulo $998\,244\,353$.

Input

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $k$ ($2 \le n \le 10^5$, $1 \le k \le n$) indicating the number of vertices in the tree and the target size of the smaller connected components.

For the following $(n - 1)$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$) indicating an edge connecting vertices $u_i$ and $v_i$ in the tree.

It’s guaranteed that the sum of $n$ of all test cases will not exceed $3 \times 10^5$.

Output

For each test case, output one line containing one integer indicating the number of ways to choose a subset $E'$ modulo $998\,244\,353$.

Examples

Input 1

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

Output 1

2
1

Note

Let $(u, v)$ be an edge connecting vertices $u$ and $v$. For the first sample test case, the two valid subsets of edges are $\{(2, 4), (3, 5)\}$ and $\{(1, 2), (3, 5)\}$.