POLSKI SPOJ

Przypomnijmy krótko bieżącą sytuację geopolityczną w Bajtlandii: nadciąga wojna domowa, a emisariusze z poszczególnych miast zjeżdżają się na Walny Zjazd (WZEMB), na którym będą ustalać przynależność swojego miasta do frakcji. Wszystko odbywa się zgodnie z następującymi zasadami.

W trakcie WZEMBu emisariusze, jeden po drugim, podchodzą do Karty z wypisaną na niej listą frakcji. Karta początkowo jest pusta. Każdy emisariusz, czytając Kartę od góry do dołu, stara się znaleźć na niej pierwszą frakcję, w skład której wchodzą wyłącznie miasta nie będące w stanie konfliktu z miastem reprezentowanym przez emisariusza. Jeżeli taka frakcja istnieje, emisariusz dołącza do niej nazwę swojego miasta; jeżeli nie -- zakłada dla swojego miasta nową frakcję, dodając wpis nowej frakcji pod wszystkimi innymi.

Jako agent obcego wywiadu próbowałeś dotychczas tak ustawić kolejność podchodzenia emisariuszy do Karty, by liczba powstających frakcji była możliwie jak największa. Niestety przełożeni (z wykształcenia matematycy) nie są zadowoleni z wyników Twoich działań, ponieważ ciężko stwierdzić, czy zaproponowane podejście jest najlepsze możliwe. Otrzymujesz długą zaszyfrowaną depeszę zawierającą:

• porcję poufnych informacji wywiadowczych: okazuje się, że każde dwa miasta Bajtlandii połączone są dokładnie jedną trasą drogową (bezpośrednio lub poprzez inne miasta), a dwa miasta znajdują się w stanie konfliktu wtedy i tylko wtedy, gdy połączone są ze sobą drogą bezpośrednio.
• instrukcje, by natychmiast zacząć poszukiwać optymalnego rozwiązania problemu.

Czas wykonać zadanie.

Wejście

W pierwszej linii pliku wejściowego podano liczbę przypadków testowych t (t=10). Każdy przypadek testowy zaczyna się od linii zawierającej liczbę całkowitą n, oznaczającą liczbę miast w Bajtlandii (1<=n<=100010). Każda z kolejnych n-1 linii zawiera parę liczb całkowitych a b oddzielonych spacją, oznaczającą, że miasta a i b połączone są drogą i znajdują się w stanie konfliktu ze sobą (1<=a,b<=n).

Wyjście

Dla każdego przypadku testowego wypisz liczbę frakcji, które powstaną w Bajtlandii, gdy poprawnie wykonasz swoje zadanie.

Przykład

Wejście:
2
3
1 2
1 3
4
1 2
2 3
3 4

Wyjście:
2
3