Алиса и Боб играют в игру на дереве $T$ с $n$ вершинами. Алиса хочет определить секретную вершину $x$. Однако Боб противодействует и не обязан выбирать $x$ заранее.

Изначально каждая вершина $T$ считается «возможным» кандидатом для $x$. Каждым ходом Алиса выбирает вершину $v$ и спрашивает расстояние от $v$ до $x$. Боб отвечает неотрицательным целым числом $d$. Затем Алиса удаляет всех кандидатов $u$, для которых $\operatorname{dist}(u, v) \neq d$.

Ответ Боба должен быть согласован хотя бы с одним оставшимся кандидатом. Другими словами, после того как Алиса удалит все вершины $u$ с $\operatorname{dist}(u, v) \neq d$, множество кандидатов всё ещё должно быть непустым. Соблюдая это правило, Боб выбирает свои ответы так, чтобы вынудить Алису использовать как можно больше запросов.

Алиса выигрывает, как только остаётся ровно один кандидат. Алиса выбирает свои запросы оптимально, чтобы минимизировать количество запросов.

Зная структуру дерева, найдите минимальное количество запросов, которое гарантирует победу Алисы независимо от стратегии Боба.

Например, если Алиса запрашивает вершину $v$, а Боб отвечает $d=2$, то все вершины на расстоянии ровно $2$ от $v$ остаются возможными, а все остальные удаляются.

Запрос к $v$ и ответ 2: заштрихованная вершина — запрошенная, пунктирные вершины остаются возможными, обычные вершины удаляются.

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

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

Каждый набор начинается с одного целого числа $n$ ($2 \le n \le 2000$) — количество вершин.

Каждая из следующих $n-1$ строк содержит два целых числа $a_i$ и $b_i$ ($1 \le a_i,b_i \le n$, $a_i \ne b_i$), обозначающих ребро дерева.

Гарантируется, что рёбра каждого набора образуют дерево и что $\sum n^2 \le 2000^2$ по всем наборам.

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

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

Примеры

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

2
4
1 2
2 3
3 4
5
1 2
1 3
1 4
1 5

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

1
3

Примечание 1

• В первом наборе дерево представляет собой путь из четырёх вершин. Запрос вершины 1 даёт возможные расстояния 0, 1, 2, 3, все различны, поэтому одного запроса достаточно.
• Во втором наборе дерево — звезда с центром в вершине 1.
• На следующих диаграммах заштрихованная вершина — запрошенная, пунктирные вершины остаются возможными после ответа Боба, а обычные удалены.

Запрос 2, ответ 2: вершины 3, 4, 5 остаются возможными.

Запрос 3, ответ 2: вершины 4, 5 остаются возможными.

Запрос 4, ответ 2: остаётся только вершина 5.

• Это показывает, что трёх запросов достаточно. Алиса сначала запрашивает лист 2. Если Боб отвечает 0 или 1, секретная вершина определяется сразу; наихудший ответ — 2, оставляя листья 3, 4, 5. Затем Алиса запрашивает лист 3, и в худшем случае остаются листья 4, 5. Последний запрос различает их.
• Двух запросов недостаточно. После первого запроса Боб может оставить возможными как минимум три листа. Среди трёх листьев звезды ещё один запрос расстояния не может различить их все, потому что как минимум два листа находятся на одинаковом расстоянии до запрошенной вершины.