Wraz z końcem epoki Średniowiecza i nastaniem Światłych Nowych Czasów, w stolicy Bajtlandii otwarto pierwsze sklepy czynne całodobowo. Mieszkańcy radośnie przyjęli tę nowość. Do czasu. Wkrótce zaobserwowano nieoczekiwany wzrost drobnej przestępczości i liczby ulicznych bójek. Burmistrz postanowił przeznaczyć część budżetu miasta na oświetlenie sieci ulic miasta, przy czym z oczywistych względów chciałby to uczynić jak najmniejszym kosztem.

Sieć dwukierunkowych ulic miasta i skrzyżowań między nimi ma następujące własności:

• Każde dwa skrzyżowania łączy co najwyżej jedna ulica.
• Istnieje dokładnie jedna trasa przejazdu z dowolnie ustalonego skrzyżowania do dowolnego innego skrzyżowania.
• Umieszczenie lampy ulicznej przy skrzyżowaniu oświetla wszystkie spotykające się w nim ulice, w związku z czym lampy postanowiono ustawiać tylko przy skrzyżowaniach.

System oświetlenia nazywamy optymalnym, jeżeli wszystkie ulice miasta są w nim oświetlone, a liczba użytych lamp jest najmniejsza możliwa.

Twoje zadanie polega na:

• Wyznaczeniu liczby lamp ulicznych w optymalnym systemie oświetlenia.
• Określeniu, spośród ilu optymalnych systemów oświetleń burmistrz może wybierać.

Wejście

W pierwszej linii wejścia podana jest liczba przypadków testowych t (t<=20). W pierwszej linii każdego przypadku testowego podana jest liczba całkowita n, określająca liczbę skrzyżowań w stolicy (1 <= n <= 100010). W kolejnych n-1 liniach podane są opisy poszczególnych ulic, w postaci pary liczb całkowitych a b, oznaczających skrzyżowania, które łączy dana ulica (1<= a,b <=n).

Wyjście

Dla każdego przypadku testowego należy wypisać linię zawierającą dwie liczby całkowite oddzielone spacją. Pierwsza z nich powinna oznaczać liczbę lamp ulicznych w optymalnym systemie oświetlenia, druga - resztę z dzielenia przez 10007 liczby różnych optymalnych systemów oświetlenia, które można zrealizować w stolicy.

Przykład

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

Wyjście:
2 3 
1 1