POLSKI SPOJ

Górska kraina

Jasiu planuje wycieczkę po malowniczych rejonach górskiej krainy, szlakami wytyczonymi przez górali. W krainie tej danych jest n miejscowości ponumerowanych liczbami naturalnymi od 1 do n, pomiędzy którymi istnieją szlaki. Z każdej miejscowości można dotrzeć pewną trasą do każdej innej miejscowości dokładnie na jeden sposób. Czas dotarcia szlakiem bezpośrednim z miejscowości a do miejscowości b równy jest |a-b|. Jasiu chce tak zaplanować swoją trasę, rozpoczynając z dowolnej miejscowości, aby trwała możliwie najdłużej, przy czym nie chce przechodzić dwa razy tym samym szlakiem. Wyznacz czas trwania wycieczki Jasia.

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (1 ≤ d ≤ 100). Dla każdego przypadku testowego w pierwszym wierszu podana jest liczba całkowita (1 ≤ n ≤ 10⁴) oznaczająca liczbę miejscowości. W kolejnych n-1 wierszach podane są po dwie liczby całkowite a, b (1 ≤ a, b ≤ n, a ≠ b) oznaczające, że pomiędzy tymi miejscowościami istnieje bezpośredni szlak, którego czas przejścia równy jest |a-b|.

Wyjście
Dla każdego przypadku należy wypisać czas najdłużej trwającej wyprawy Jasia. Pliki wejścia nie przekraczają 5MB.

Przykład

Wejście
1
7
1 7
7 6
1 4
7 3
6 2
4 5

Wyjście
15


Wyjaśnienie: najdłużej trwająca wyprawa to trasa pomiędzy miejscowościami 2-6-7-1-4-5. Czas przejścia równy jest 15.