Тимур решил заняться пробежками по общежитию. Он мотивирует себя блинами.

Общежитие состоит из $n$ комнат, некоторые пары из которых соединены переходами длиной 10 метров. Общежитие является деревом, то есть для каждой пары комнат существует ровно один путь их соединяющий.

Каждая комната содержит тарелку, в которой находится ровно $k$ блинов. Каждый переход содержит тарелку, в которой находится ровно 2 блина.

Пробежка Тимура выглядит следующим образом:

1. Тимур стартует в любой из комнат и ест в ней 1 блин. Переходит к шагу 2.
2. Тимур, находясь в комнате $v$, выбирает некоторую комнату $u$, такую, что:
   • Переход между $v$ и $u$ существует и содержит хотя бы 1 блин.
   • Комната $u$ содержит хотя бы 1 блин. Если такой комнаты не существует, Тимур расстраивается и немедленно прекращает пробежку. Иначе он переходит к шагу 3.
3. Тимур перебегает из $v$ в $u$, съедая по одному блину в переходе между ними и в комнате $u$, после чего возвращается к шагу 2.

Тимуру стало интересно, какое максимальное количество метров он сможет пробежать, если выберет стратегию оптимально. Помогите ему определить это.

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

Первая строка теста содержит одно целое число $t$ ($t ⩽ 100$) — количество наборов тестовых данных. Затем следуют $t$ наборов тестовых данных, разделенные пустой строкой. Первая строка набора тестовых данных содержит два целых числа $n, k$ ($1 ⩽ n ⩽ 10^5, 1 ⩽ k ⩽ 10^9$). Следующая $n − 1$ строка набора тестовых данных содержит два целых числа $v, u$ ($1 ⩽ v, u ⩽ n, u \neq v$) — описание переходов. Гарантируется, что переходы задают дерево. Гарантируется, что сумма $n$ в тестовых наборах не превосходит $10^5$ .

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

Для каждого набора тестовых данных выведите в отдельной строке одно целое число — ответ на него.

Система оценки

Каждый тест в каждой группе независимо оценивается в 5 баллов.

Подзадачи