FRAKTAL - konkurs programistyczny

W Bajtlandii urząd króla sprawuje dzielny Bajtomir. Znany ze swojej waleczności na całym kontynencie, poprowadził swój kraj do zwycięstwa w wojnie z Bitlandią. Nastały jednak czasy pokoju i król dla odmiany zadecydował zainwestować pieniądze w kulturę. Postanowił wybudować w wybranych miastach teatry. Ponieważ fundusze ma ograniczone wolałby nie budować teatru w każdym mieście. Aby jednak zminimalizować niezadowolenie mieszkańców wymyślił jak można efektywnie rozplanować ich budowę: niech każde miasto zawiera teatr lub jest w bezpośrednim sąsiedztwie z jakimś miastem zawierającym teatr. Dwa miasta są w bezpośrednim sąsiedztwie jeśli istnieje droga je łącząca.

Jako inżynier króla zaobserwowałeś ciekawą własność sieci dróg Bajtlandii: pomiędzy każdą parą miast istnieje dokładnie jedna ścieżka je łącząca. Teraz pozostaje tylko wyliczenie ile minimalnie teatrów należy zbudować.

Wejście

Wejście rozpoczyna liczba testów 1 ≤ t ≤ 10. Następnie podawane są kolejne testy.

Pojedynczy test rozpoczyna liczba 1 ≤ n ≤ 10⁵ oznaczająca liczbę miast Bajtlandii. W kolejnych n-1 liniach podany jest opis sieci dróg kraju. W każdej linii znajdują się dwie liczby 1 ≤ a, b ≤ n; a ≠ b oznaczające istnienie bezpośredniego połączenia między miastami a oraz b.

Wyjście

Dla każdego testu wynik należy podać w osobnej linii. Wynikiem jest minimalna liczba teatrów które należy wybudować w miastach Bajtlandii, aby spełnione były wymagania Bajtomira.

Przykład

Wejście:

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

Wyjście:

2
1