Po pomyślnym rozwiązaniu problemu Cut Cut Cut!, Little Cyan Fish stara się dalej doskonalić swoje umiejętności w partycjonowaniu spójnych składowych w grafach.

Pewnego dnia Little Cyan Fish otrzymuje od tajemniczego mędrca wyjątkowe zadanie. Otrzymuje drzewo nieskierowane zawierające $n$ wierzchołków oraz liczbę całkowitą $k$. Niech $E$ oznacza zbiór wszystkich krawędzi w drzewie. Celem Little Cyan Fish jest wskazanie podzbioru $E' \subseteq E$. Po usunięciu wszystkich krawędzi z $E'$, graf powinien rozpaść się na kilka spójnych składowych, z których każda ma rozmiar równy $k$ lub $(k + 1)$.

Jako ekspert w dziedzinie partycjonowania, Little Cyan Fish sprawnie rozwiązuje ten problem. Jednak ciekawość tajemniczego mędrca wykracza poza samo mistrzostwo. Pragnie on zbadać wszystkie potencjalne wyniki. W związku z tym zleca Little Cyan Fish wyznaczenie całkowitej liczby różnych sposobów wyboru podzbioru $E' \subseteq E$, spełniającego podany warunek. Dwa sposoby uważa się za różne, jeśli wybrane podzbiory krawędzi są różne.

Pomóż Little Cyan Fish ukończyć to wyzwanie. Ponieważ wynik może być duży, należy podać go modulo $998\,244\,353$.

Wejście

Dostępnych jest wiele przypadków testowych. Pierwsza linia wejścia zawiera liczbę całkowitą $T$ oznaczającą liczbę przypadków testowych. Dla każdego przypadku testowego:

Pierwsza linia zawiera dwie liczby całkowite $n$ oraz $k$ ($2 \le n \le 10^5$, $1 \le k \le n$), oznaczające liczbę wierzchołków w drzewie oraz docelowy rozmiar mniejszych spójnych składowych.

W kolejnych $(n - 1)$ liniach, $i$-ta linia zawiera dwie liczby całkowite $u_i$ oraz $v_i$ ($1 \le u_i, v_i \le n$), oznaczające krawędź łączącą wierzchołki $u_i$ oraz $v_i$ w drzewie.

Gwarantuje się, że suma $n$ dla wszystkich przypadków testowych nie przekroczy $3 \times 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz w jednej linii jedną liczbę całkowitą oznaczającą liczbę sposobów wyboru podzbioru $E'$ modulo $998\,244\,353$.

Przykład

Wejście 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

Wyjście 1

2
1

Uwagi

Niech $(u, v)$ będzie krawędzią łączącą wierzchołki $u$ oraz $v$. Dla pierwszego przykładowego przypadku testowego, dwoma poprawnymi podzbiorami krawędzi są $\{(2, 4), (3, 5)\}$ oraz $\{(1, 2), (3, 5)\}$.