Зет — это Самость, а Самость — это Зет
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В компьютерной игре Dota 2 есть герой Arc Warden. Его ультимейт создает своего клона, который обладает всеми способностями героя. Карта представляет собой дерево из $$$n$$$ вершин с нейтральным крипом в каждой вершине. Напомним, что деревом называется связный неориентированный граф без циклов. Зафармив крипов, герой может получить опыт и золото.

Arc Warden хочет посетить все вершины и зафармить всех крипов. Для этого он выбирает начальную вершину, встаёт в неё и создает своего клона в той же вершине. Затем они с клоном независимо обходят дерево, переходя в соседние по ребру вершины. Разрешается посещать одну вершину более одного раза.

Определите минимальное суммарное расстояние, которое Arc Warden и его клон должны пройти по дереву, чтобы посетить каждую вершину. Расстояние считается как количество рёбер.

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

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 500$$$) — количество наборов входных данных.

Первая строка теста содержит целое число $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — количество вершин в дереве.

Следующие $$$n-1$$$ строк описывают рёбра дерева, где каждое ребро соединяет пару вершин $$$u$$$ и $$$v$$$ ($$$1 \leq u,v \leq n$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — минимальное суммарное расстояние, которое должны пройти Arc Warden и его клон, чтобы обойти всё дерево.

Пример

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

    351 22 34 25 486 15 88 36 77 52 14 722 1

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

    5
    8
    1

Примечание

В первом наборе входных данных выгодно начать в вершине $$$2$$$. Arc Warden может пройти путь $$$2 \to 3 \to 2 \to 1$$$, а его клон может пройти путь $$$2 \to 4 \to 5$$$. Таким образом, суммарно будет пройдено $$$5$$$ рёбер. Можно показать, что ответ лучше получить нельзя.