4. i-Build

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\).