Alice y Bob juegan un juego en un árbol $T$ con $n$ vértices. Alice quiere identificar un vértice secreto $x$. Sin embargo, Bob es adversario y no tiene que elegir $x$ de antemano.

Inicialmente, cada vértice de $T$ se considera un candidato "posible" para $x$. En cada turno, Alice elige un vértice $v$ y pregunta la distancia desde $v$ hasta $x$. Bob responde con un entero no negativo $d$. Alice entonces elimina todo vértice candidato $u$ tal que $\operatorname{dist}(u, v) \neq d$.

La respuesta de Bob debe ser consistente con al menos un candidato restante. En otras palabras, después de que Alice elimine todos los vértices $u$ con $\operatorname{dist}(u, v) \neq d$, el conjunto de candidatos debe seguir siendo no vacío. Sujeto a esta regla, Bob elige sus respuestas para obligar a Alice a usar la mayor cantidad posible de consultas.

Alice gana tan pronto como quede exactamente un vértice candidato. Alice elige sus consultas de manera óptima para minimizar el número de consultas.

Dada la estructura del árbol, encuentre el número mínimo de consultas que Alice necesita para garantizar la victoria, independientemente de la estrategia de Bob.

Por ejemplo, si Alice consulta un vértice $v$ y Bob responde $d=2$, entonces todos los vértices a distancia exactamente $2$ de $v$ siguen siendo posibles, y todos los demás vértices son eliminados.

Consultando $v$ y recibiendo la respuesta 2: el vértice sombreado es el consultado, los vértices punteados siguen siendo posibles y los vértices sin relleno son eliminados.

Entrada

La primera línea contiene un entero $t$ ($1 \le t \le 10^5$), el número de casos de prueba.

Cada caso de prueba comienza con un entero $n$ ($2 \le n \le 2000$), el número de vértices.

Cada una de las siguientes $n-1$ líneas contiene dos enteros $a_i$ y $b_i$ ($1 \le a_i,b_i \le n$, $a_i \ne b_i$), indicando una arista del árbol.

Se garantiza que las aristas de cada caso de prueba forman un árbol y que $\sum n^2 \le 2000^2$ sobre todos los casos de prueba.

Salida

Para cada caso de prueba, imprima un entero: el número mínimo de consultas que Alice necesita en el peor caso.

Ejemplos

Entrada 1

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

Salida 1

1
3

Nota

• En el primer caso de prueba, el árbol es un camino de cuatro vértices. Consultar el vértice 1 da distancias posibles 0, 1, 2, 3, todas distintas, por lo que una consulta es suficiente.
• En el segundo caso de prueba, el árbol es una estrella centrada en el vértice 1:
• En los siguientes diagramas, el vértice sombreado es el vértice consultado, los vértices punteados siguen siendo posibles después de la respuesta de Bob, y los vértices sin relleno han sido eliminados.

Consulta 2, respuesta 2: los vértices 3, 4, 5 siguen siendo posibles.

Consulta 3, respuesta 2: los vértices 4, 5 siguen siendo posibles.

Consulta 4, respuesta 2: solo queda el vértice 5.

• Esto muestra que tres consultas son suficientes. Alice primero consulta la hoja 2. Si Bob responde 0 o 1, el secreto se determina inmediatamente; la peor respuesta es 2, dejando las hojas 3, 4, 5. Luego Alice consulta la hoja 3, y en el peor caso quedan las hojas 4, 5. Una consulta final las distingue.
• Dos consultas no son suficientes. Después de la primera consulta, Bob puede mantener al menos tres hojas posibles. Entre tres hojas de una estrella, una consulta de distancia más no puede distinguirlas todas, porque al menos dos de las hojas tienen la misma distancia al vértice consultado.