G. Развал дерева
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево$$$^{\text{∗}}$$$ из $$$n$$$ вершин. Вы можете один раз выбрать две вершины $$$a$$$ и $$$b$$$ и удалить все вершины на пути из $$$a$$$ в $$$b$$$, включая сами вершины. Если вы выберете $$$a=b$$$, то будет удалена только одна вершина.

Ваша задача — найти максимальное количество компонент связности$$$^{\text{†}}$$$, которое может образоваться после удаления пути из дерева.

$$$^{\text{∗}}$$$Деревом называется связный граф без циклов.

$$$^{\text{†}}$$$Компонента связности это такое множество вершин, в котором из каждой вершины можно попасть по рёбрам в любую другую (и нельзя попасть в вершины, не принадлежащие этому множеству)

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

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

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — размер дерева.

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

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

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

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

Пример
Входные данные
6
2
1 2
5
1 2
2 3
3 4
3 5
4
1 2
2 3
3 4
5
2 1
3 1
4 1
5 4
6
2 1
3 1
4 1
5 3
6 3
6
2 1
3 2
4 2
5 3
6 4
Выходные данные
1
3
2
3
4
3