4. Tradičné zimné slávnosti

Obec Kmeťovo, ktorá leží v blízkosti Nových Zámkov je veľmi veselé miesto na žitie. Keď sa prechádzate jeho ulicami, neraz sa vám stane, že odvšadiaľ počuť výbuchy smiechu a radosti, proste samé “Hihihi”, “Hahaha”.

Dôvodom takéhoto šťastného nažívania je skvelý pán starosta, ktorý organizuje spoločenský a kultúrny život v dedinke. Každoročne usporadúva Tradičné jarné, letné, jesenné aj zimné slávnosti, na ktorých sa všetci veselia, pijú a hodujú¹. A samozrejme, na blížiace sa tradičné zimné slávnosti sa pozýva veľké množstvo tradičných karnevalových sprievodov.

Kvôli tradičnému socialistickému návrhu stavania obcí, je topológiou obce strom. Inak povedané obec Kmeťovo tvoria križovatky pospájané ulicami pričom platí, že medzi každou dvojicou križovatiek existuje práve jedna cesta skladajúca sa za viacerých ulíc.

Naviac, do obce a von z nej sa dá dostať iba cez križovatky, ktoré v strome predstavujú listy, teda sú pripojené iba k jednej križovatke vo vnútri obce.

Pán starosta by chcel do Kmeťova pozvať čo najviac sprievodov, ktoré vojdú do dediny cez nejakú križovatku a potom inou križovatkou vyjdú von, pričom nemôžu prejsť cez žiadnu ulicu dvakrát, čím je ich cesta dedinou jednoznačne určená. Avšak, ako ho upozornil jeden z členov rady obce, nie je rozumné, aby cez nejakú ulicu prešlo priveľa sprievodov, lebo také dupotanie slonov môže vážne narušiť statiku budov. Pre každú ulicu preto určili maximálny počet sprievodov, ktoré ňou môžu prejsť. Teraz sedia nad plánmi dediny a márne premýšľajú, koľko najviac karnevalov vedia pozvať do Kmeťova.

Úloha

Na vstupe dostanete niekoľko stromov s ohodnotenými hranami. Pre každý z nich nás bude zaujímať jedno číslo: najväčší počet ciest od jedného listu k druhému, ktoré vieme vybrať tak, aby po každej hrane išlo nanajvýš toľko ciest, aká je jej hodnota. Dvojicu listov môžeme vybrať viackrát.

Formát vstupu

Na prvom riadku vstupu je číslo \(z\) – počet vstupných sád. Nasleduje \(z\) vstupných sád. Každá začína číslom \(n\) (\(2 \leq n \leq 10^5\)) – počtom vrcholov. Za ním nasleduje \(n-1\) riadkov, každý s trojicou čísel \(x\), \(y\), \(c\) (\(1 \leq x,y \leq n\), \(1 \leq c \leq 10^6\)) s nasledovným významom: medzi vrcholmi \(x\) a \(y\) vedie hrana s hodnotou \(c\).

Môžete predpokladať, že každý graf na vstupe je naozaj súvislý strom.

Formát výstupu

Pre každú vstupnú sadu vypíšte jeden riadok obsahujúci jedno číslo – najväčší počet ciest, ktoré vieme vybrať spĺňajúc podmienky zadania.

Príklad

Input:

3
4
1 2 2
1 3 2
1 4 2
2
1 2 2
3
1 2 2
2 3 1

Output:

3
2
1

V prvej sade sú listovými vrcholy \(2\), \(3\), \(4\) a jediná možnosť, ako spomedzi nich vybrať 3 dvojice je vybrať každú dvojicu raz.

V druhej sade máme len dva vrcholy, každý má len jedného suseda, čiže oba sú listové. Vyberieme ich dvakrát.

V tretej sade sú listovými vrcholy \(1\) a \(3\), vybrať ich vieme len raz.