Alice et Bob jouent à un jeu sur un arbre $T$ à $n$ sommets. Alice souhaite identifier un sommet secret $x$. Cependant, Bob est un adversaire et n'a pas à choisir $x$ à l'avance.

Initialement, chaque sommet de $T$ est considéré comme un candidat « possible » pour $x$. À chaque tour, Alice choisit un sommet $v$ et demande la distance de $v$ à $x$. Bob répond par un entier non négatif $d$. Alice supprime alors tout sommet candidat $u$ tel que $\operatorname{dist}(u, v) \neq d$.

La réponse de Bob doit être cohérente avec au moins un candidat restant. En d'autres termes, après qu'Alice a supprimé tous les sommets $u$ avec $\operatorname{dist}(u, v) \neq d$, l'ensemble des candidats doit encore être non vide. Sous réserve de cette règle, Bob choisit ses réponses pour forcer Alice à utiliser autant de requêtes que possible.

Alice gagne dès qu'il ne reste plus qu'un seul sommet candidat. Alice choisit ses requêtes de manière optimale pour minimiser le nombre de requêtes.

Étant donnée la structure de l'arbre, trouvez le nombre minimal de requêtes dont Alice a besoin pour garantir une victoire, quelle que soit la stratégie de Bob.

Par exemple, si Alice interroge un sommet $v$ et que Bob répond $d=2$, alors tous les sommets à distance exactement $2$ de $v$ restent possibles, et tous les autres sommets sont supprimés.

Interroger $v$ et recevoir la réponse 2 : le sommet hachuré est interrogé, les sommets pointillés restent possibles, et les sommets pleins sont supprimés.

Entrée

La première ligne contient un entier $t$ ($1 \le t \le 10^5$), le nombre de cas de test.

Chaque cas de test commence par un entier $n$ ($2 \le n \le 2000$), le nombre de sommets.

Chacune des $n-1$ lignes suivantes contient deux entiers $a_i$ et $b_i$ ($1 \le a_i,b_i \le n$, $a_i \ne b_i$), dénotant une arête de l'arbre.

Il est garanti que les arêtes de chaque cas de test forment un arbre et que $\sum n^2 \le 2000^2$ sur tous les cas de test.

Sortie

Pour chaque cas de test, affichez un entier : le nombre minimal de requêtes dont Alice a besoin dans le pire des cas.

Exemples

Entrée 1

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

Sortie 1

1
3

Remarque 1

• Dans le premier cas de test, l'arbre est un chemin de quatre sommets. Interroger le sommet 1 donne les distances possibles 0, 1, 2, 3, toutes distinctes, donc une requête suffit.
• Dans le second cas de test, l'arbre est une étoile centrée au sommet 1 :

Dans les diagrammes suivants, le sommet hachuré est le sommet interrogé, les sommets pointillés restent possibles après la réponse de Bob, et les sommets pleins ont été supprimés.

Interrogation 2, réponse 2 : les sommets 3, 4, 5 restent possibles.

Interrogation 3, réponse 2 : les sommets 4, 5 restent possibles.

Interrogation 4, réponse 2 : seul le sommet 5 reste.

• Cela montre que trois requêtes sont suffisantes. Alice interroge d'abord la feuille 2. Si Bob répond 0 ou 1, le secret est immédiatement déterminé ; la pire réponse est 2, laissant les feuilles 3, 4, 5. Ensuite Alice interroge la feuille 3, et dans le pire des cas, les feuilles 4, 5 restent. Une dernière requête les distingue.
• Deux requêtes ne suffisent pas. Après la première requête, Bob peut garder au moins trois feuilles possibles. Parmi trois feuilles d'une étoile, une requête de distance supplémentaire ne peut pas toutes les distinguer, car au moins deux des feuilles ont la même distance au sommet interrogé.