SPOJ Brasil

O Comitê Internacional da Cruz Vermelha, organização sem fins lucrativos cujo objetivo é defender e amparar as vítimas de guerras (ou melhor, vítimas do capital) ou catástrofes naturais, ganhou os prêmios Nobel de 1917, 1945 e 1963 pelo seu importantíssimo trabalho. Como é de se imaginar, a Cruz Vermelha sempre teve problemas de locomoção no meio da guerra. Muitas ligações (estradas, ferrovias etc) entre cidades de países em guerra podem ser destruídas por bombardeios ou dominadas por tiranos.

O departamento de inteligência da Cruz Vermelha está empenhado em criar um programa de computador que auxilie as operações da Cruz Vermelha no futuro. A idéia é, dado um mapa da região que será ajudada, determinar em quais cidades devem ser feitas as bases da Cruz Vermelha. Inicialmente, o Departamento está interessado em testar a primeira versão do programa em cidades com as seguintes características: (a) sempre existe um caminho entre duas cidades que passa por uma ou mais ligações; (b) não existem dois caminhos diferentes entre duas cidades quaisquer. Apesar dos recursos da Cruz Vermelha geralmente serem limitados, eles querem escolher o maior número possível de bases, e garantir que ou existe uma base na cidade ou existe uma base em uma cidade vizinha, com a restrição adicional de que não é permitido criar bases em duas cidades vizinhas.

Esta última restrição é dada pelo fato de que se estivesse em período de guerra, a Cruz Vermelha, como sabemos deve ter livre acesso nas cidades, e com isso pode surgir a suspeita de espionagem, o que pode comprometer o objetivo principal da organização.

Sua tarefa é escrever a primeira versão do programa que o Departamento quer testar.

Entrada

A primeira linha de um caso de teste possui um inteiro T que indica o número de instâncias seguintes. A primeira linha de cada instância possui um inteiro N (1 ≤ N ≤ 6000) indicando o número de cidades do mapa. As cidades são identificadas por 1, 2, ..., N. As próximas N-1 linhas possuem dois inteiros u e v (1 ≤ u, v ≤ N, u != v) que indicam uma ligação entre as cidades u e v (considere que tais ligações permitem acesso de u até v e de v até u).

Saída

Para cada instância imprima uma inteiro indicando o número máximo de bases que a Cruz Vermelha consegue construir levando-se em consideração as restrições descritas anteriormente.

Exemplo de entrada
2
10
1 2
1 3
2 4
2 5
2 6
3 7
7 8
7 9
7 10
5
1 2
1 3
2 4
2 5

Exemplo de saída
7
3