E. Красивые подграфы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Монокарпа есть дерево, состоящее из $$$n$$$ вершин.

Он планирует выбрать некоторую вершину $$$r$$$ и проделать следующие операции над каждой вершиной $$$v$$$ от $$$1$$$ до $$$n$$$:

  • присвоить $$$d_v$$$ равным расстоянию от $$$v$$$ до $$$r$$$ (количество ребер на кратчайшем пути);
  • раскрасить $$$v$$$ в какой-нибудь цвет.

Раскраска называется красивой, если она удовлетворяет двум условиям:

  • для каждой пары вершин одного цвета $$$(v, u)$$$ существует путь из $$$v$$$ в $$$u$$$, который посещает только вершины того же цвета;
  • для каждой пары вершины одного цвета $$$(v, u)$$$, $$$d_v \neq d_u$$$.

Обратите внимание, что Монокарп может выбирать любое количество различных цветов, которые он хочет использовать.

Для каждого использованного цвета он затем считает количество вершин этого цвета. Стоимость дерева — это минимум из этих значений.

Какая может быть наибольшая стоимость дерева?

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

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

В первой строке записано одно целое число $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — количество вершин в дереве.

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

Заданные ребра образуют дерево. Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

На каждый набор входных данных выведите одно целое число — наибольшая возможная стоимость дерева.

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