En el reino de WALandia, el rey Luis debe elegir ciudades para colocar estaciones de guardia real. El reino está formado por ~N~ ciudades conectadas por ~N-1~ caminos, formando un árbol. Una estación de guardia en una ciudad protege esa ciudad y todas las ciudades directamente conectadas a ella. El rey Luis quiere proteger todas las ciudades del reino con la mínima cantidad de estaciones de guardia posibles.

Tu tarea es ayudarlo a determinar cuántas estaciones de guardia necesita construir para cada uno de los ~T~ reinos que gobierna.

Entrada

La primera línea contiene un entero ~T~ ~(1 \leq T \leq 10^4)~, el número de casos de prueba.

Para cada caso de prueba:

• La primera línea contiene un entero ~N~ ~(1 \leq N \leq 2 \cdot 10^5)~, el número de ciudades del reino.
• Las siguientes ~N-1~ líneas contienen dos enteros ~u~ y ~v~ ~(1 \leq u, v \leq N, u \neq v)~, indicando que hay un camino entre la ciudad ~u~ y la ciudad ~v~.

Se garantiza que la suma de ~N~ sobre todos los casos de prueba no excede ~2 \cdot 10^5~.

Salida

Para cada caso de prueba, imprime un entero: la cantidad mínima de estaciones de guardia necesarias para ese reino.

Ejemplo de Entrada

3
7
1 2
1 3
2 4
2 5
3 6
3 7
4
1 2
2 3
3 4
1

Ejemplo de Salida

2
2
1

Explicaciones

Primer caso: Hay 7 ciudades. Colocando guardias en las ciudades 2 y 3 se protegen todas las ciudades (la ciudad 2 cubre ~{1,2,4,5}~ y la ciudad 3 cubre ~{1,3,6,7}~). La respuesta es 2.

Segundo caso: Es una línea de 4 ciudades. Se necesitan 2 estaciones (en las ciudades 2 y 4, por ejemplo).

Tercer caso: Solo hay una ciudad. Se necesita 1 estación en ella.