Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_04_03 - Egipcjanin PRK

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


Dodane przez:Krzysztof Lewko
Data dodania:2013-02-01
Limit czasu wykonania programu:1s-3s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:AlgoLiga 4
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.