AlgoLiga 2018

PRK zainspirowany egispskimi piramidami postanowił zbudować swoje. Ma w swoim domu bardzo dużo klocków o wymiarach 1x1xK ( dla dowolnie dużego K ). Jego pomysł na piramidę wygląda następująco: najdłuższy klocek leży na samym dole, według tej zasady, kolejne mniejsze piramidki mogą być zbudowane na niższym klocku. Odległość sąsiednich klocków od siebie powinna wynosić 1 oraz odległość klocków, a krawędzią podstawy na której leżą także powinna wynosić 1. Na czubku każdej wieży musi znajdować się klocek o długości 1. PRK bardzo szybko ową zasadę przerobił na pojęcie informatyczne, a konkretniej ukorzenione drzewo.


Korzeń drzewa jest podstawą budowli, łączy się się ona z kolejnymi blokami, a liściami są klocki o wymiarach 1x1x1.
PRK opanował swoje budowle do perfekcji, dlatego daje tobie następującą zagadę: Znając tylko strukturę drzewa, jaka jest całkowita objętość oryginalnej budowli?
Załóż, że korzeń drzewa to wierzchołek o indeksie 0.

Input
W pierwszym wierszu podana jedna liczba T ( 1 <= T <= 100 ) oznaczająca liczbę testów.
Każdy test składa się z następującego opisu :
W pierwszym wierszu liczba N ( 1 <= N <= 1000 ) oznaczająca liczbę wierzchołków drzewa.
W kolejnych N-1 wierszach po dwie liczby a,b ( 0 <= a,b < N ) oznaczające połączenie między tymi dwoma wierzchołkami.

Output
Dla każdego testu w osobnej linii jedna liczba: objętość danej piramidy.

Example
Input:
2
7
0 1
2 0
0 3
2 4
5 2
6 3
3
1 2
1 0
Output:
25
9