После успешного решения задачи Cut Cut Cut!, Маленькая Голубая Рыбка стремится отточить свои навыки в разбиении связных компонентов в графах.

Однажды таинственный мудрец бросает вызов Маленькой Голубой Рыбке, предлагая уникальную задачу. Ему дано дерево без корня, содержащее $n$ вершин, и целое число $k$. Пусть $E$ — множество всех ребер в дереве. Цель Маленькой Голубой Рыбки — определить подмножество $E' \subseteq E$. После удаления всех ребер из $E'$ граф должен распасться на несколько связных компонентов, каждый из которых имеет размер либо $k$, либо $(k + 1)$.

Будучи экспертом в разбиениях, Маленькая Голубая Рыбка легко решает эту задачу. Однако любопытство таинственного мудреца выходит за рамки простого мастерства. Он хочет изучить все возможные исходы. Вследствие этого он поручает Маленькой Голубой Рыбке определить общее количество различных способов выбора $E' \subseteq E$, удовлетворяющих указанному условию. Два способа считаются различными, если выбранные подмножества ребер различаются.

Помогите Маленькой Голубой Рыбке справиться с этим вызовом. Поскольку ответ может быть очень большим, вам нужно вывести его по модулю $998\,244\,353$.

Входные данные

Имеется несколько тестовых случаев. Первая строка входных данных содержит целое число $T$, указывающее количество тестовых случаев. Для каждого тестового случая:

Первая строка содержит два целых числа $n$ и $k$ ($2 \le n \le 10^5$, $1 \le k \le n$), указывающие количество вершин в дереве и целевой размер меньших связных компонентов.

Следующие $(n - 1)$ строк содержат по два целых числа $u_i$ и $v_i$ ($1 \le u_i, v_i \le n$), указывающие ребро, соединяющее вершины $u_i$ и $v_i$ в дереве.

Гарантируется, что сумма $n$ по всем тестовым случаям не превышает $3 \times 10^5$.

Выходные данные

Для каждого тестового случая выведите одну строку, содержащую одно целое число — количество способов выбрать подмножество $E'$ по модулю $998\,244\,353$.

Примеры

Примеры 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

Выходные данные 1

2
1

Примечание

Пусть $(u, v)$ — ребро, соединяющее вершины $u$ и $v$. Для первого примера тестового случая двумя допустимыми подмножествами ребер являются $\{(2, 4), (3, 5)\}$ и $\{(1, 2), (3, 5)\}$.