Denis sa v lete vybral na brigádu do továrne na kreatívne detské hračky, ktorú vlastní známa americká technologická firma. Zakladatelia tejto značky prišli s nápadom používať pri výrobe hračiek pre deti praktické a život zachráňujúce materiály. Napríklad, časti ich stavebnice sú vyrobené zo špeciálnej hmoty, ktorá pohlcuje radiáciu a tým chráni a lieči deti.

Stavebnica sa skladá z hranolov s rozmermi $1\,cm$, $1\,cm$ a $n\,cm$. Hranoly stavebnice sa ukladajú vždy len rovnobežne na seba, čím vytvárajú akési veže tak, ako je to znázornené na obrázku (pohľad z boku).

Platia pri tom tieto pravidlá:

• Vrch veže (hranol, na ktorom už nie je položený iný hranol) je kocka s rozmermi $1\,cm$, $1\,cm$ a $1\,cm$.

• Hranol $a$ položený na hranole $b$ je kratší než hranol $b$.

• Medzi podstavami (spodkami) veží je medzera $1\,cm$.

• Medzi koncom hranola a podstavou veže je $1\,cm$.

Denis má k dispozícii len istý opis stavebnice. Každý hranol má svoje číslo $x$ ($0 \leq x < n$), pričom $n$ je počet hranolov v stavebnici. Denis dostane len zoznam $n-1$ dvojích hranolov $a$ a $b$, ktoré sa dotýkajú (jeden je položený na druhom). To sa dá reprezentovať ako stromový graf ako na obrázku, pričom jeho koreň je v najdlhšom hranole a ten má vždy číslo $0$.

Denisovou úlohou je presne zistiť, koľko centimetrov kubických hmoty je potrebných na výrobu konkrétnej stavebnice. Pomôžete mu?

Formát vstupu

Na prvom riadku vstupu je číslo $t$ udávajúce počet stavebníc. Nasleduje popis $t$ stavebníc. Na prvom riadku stavebnice je číslo $n$, ktoré hovorí o počte hranolov. Nasleduje $n-1$ dvojíc hranolov $a$ a $b$, ktoré znamenajú, že hranoly $a$ a $b$ sa dotýkajú.

Platí $1 \leq t \leq 500$ a $1 \leq$ súčet $n \leq 200\,000$.

Formát výstupu

Pre každú stavebnicu vypíšte jedno celé číslo udávajúce objem stavebnice v $cm^3$ ($cm^3$ nevypisujte).

Príklady

Input:

2
7
0 1
2 0
0 3
2 4
5 2
6 3
3
1 2
1 0

Output:

25
9

Na vstupe sú dve stavebnice. Prvá z nich je zobrazená aj na obrázku vyššie. Druhá z nich je jednoduchšia - je to pyramída výšky $3$, kde najspodnejší hranol $0$ má dĺžku $5$, na ňom hranol $1$ má dĺžku $3$ a vrchný hranol $2$ má dĺžku $1$. To je dokopy objem $9cm^3$.