C. Стрижка деревьев
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано дерево с $$$n$$$ вершинами, корень которого находится в вершине $$$1$$$. В этой задаче лист — это некорневая вершина со степенью $$$1$$$.

За одну операцию можно удалить лист и смежное с ним ребро (возможно, появятся новые листья). Какое минимальное количество операций нужно выполнить, чтобы получилось дерево, также с корнем в вершине $$$1$$$, в котором все листья находятся на одинаковом расстоянии от корня?

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

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

Каждая из следующих $$$n-1$$$ строк содержит два целых числа $$$u$$$, $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$), описывающих ребро, соединяющее $$$u$$$ и $$$v$$$. Гарантируется, что заданные ребра образуют дерево.

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

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

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

Пример
Входные данные
3
7
1 2
1 3
2 4
2 5
4 6
4 7
7
1 2
1 3
1 4
2 5
3 6
5 7
15
12 9
1 6
6 14
9 11
8 7
3 5
13 5
6 10
13 15
13 6
14 12
7 2
8 1
1 4
Выходные данные
2
2
5
Примечание

В первых двух наборах входных данных деревья выглядят так:

В первом наборе входных данных, удалив ребра $$$(1, 3)$$$ и $$$(2, 5)$$$, вы получите дерево, у которого все листья (вершины $$$6$$$ и $$$7$$$) находятся на одинаковом расстоянии от корня (вершины $$$1$$$), которое равняется $$$3$$$. Ответ — $$$2$$$, так как это минимальное количество ребер, которое нужно удалить для достижения цели.

Во втором наборе входных данных удаление ребер $$$(1, 4)$$$ и $$$(5, 7)$$$ приводит к дереву, в котором все листья (вершины $$$4$$$ и $$$5$$$) находятся на одинаковом расстоянии от корня (вершины $$$1$$$), которое равняется $$$2$$$.