Toska

Eu zic omul sa fie multumit cu saracia sa, caci, daca e vorba, nu bogatia, ci linistea colibei tale te face fericit
— Gluma e ca gen, e moara cu noroc, e gen, o gluma de liceu, nu stiu daca va prindeti.
Ioan Slavici, Mare Clasic

Cerință

Egor, afectat de vremea mohorâtă de iarnă, alege să-și petreacă timpul cu o activitate creativă pentru a-și îmbunătăți starea de spirit — pictura. Astfel, a decis să iasă din casă și să admire natura. Plimbându-se prin Cișmigiu, a observat unul dintre cei mai deosebiți arbori pe care i-a văzut vreodată: un arbore informatic.

Arborele are $N$ noduri, iar fiecare ramură (muchie) a acestui arbore are o culoare specifică, făcând treaba lui de artist mult mai complicată.

Lui Egor îi place mult simetria, de aceea a decis să accentueze în pictura sa un lanț$^1$ în care toate culorile muchiilor din lant apar de un număr par de ori$^2$. Totuși, el este adesea indecis; înainte de a alege lanțul pe care îl va accentua, ar dori să știe numărul de lanțuri care ar îndeplini criteriul descris anterior. Ajută-l să afle acest număr!

Date de intrare

Pe prima linie se va afla un singur număr întreg $T$ — numarul de scenarii diferite.

Fiecare scenariu va fi descris în modul următor:

• prima linie va contine un număr întreg $N$ — numărul de noduri din arbore;
• următoarele $N-1$ linii vor descrie arborele. A $i$-a linie va conține câte 3 numere întregi $u_i, v_i, c_i$, reprezentând o muchie de la $u_i$ la $v_i$ de culoare $c_i$.

Date de ieșire

Se vor afișa $T$ linii. A $i$-a linie va conține un singur număr întreg, reprezentând răspunsul pentru al $i$-lea scenariu.

Restricții și precizări

• $^1$: Un lanț într-un arbore care unește două noduri $x$ și $y$ este o secvență de lungime minimă de muchii care leagă nodul $x$ de nodul $y$.
• $^2$: Se consideră că o culoare apare de un număr par de ori într-un lanț dacă frecvența acesteia în multimea culorilor muchiilor ce alcătuiesc lanțul este pară;
• $1 \leq T \leq 200\ 000$;
• Suma $N$-urilor pentru toate scenariile (notată mai jos cu $S_N$) nu depăseste $200\ 000$;
• $1 \le c_i \le N$;
• $1 \leq u_i, v_i \leq N, u_i \neq v_i$ și nu există $i, j$ astfel încât $u_i = u_j$ și $v_i = v_j$ (sau viceversa);
• Se garantează că arborele este conex;
• Este recomandată calcularea răspunsului utilizând tipuri de date pe $64$ de biți.

Subtask-uri

Exemplul 1

stdin

2
8
1 5 7
8 1 1
8 6 1
2 7 4
1 4 7
1 2 4
1 3 7
16
2 8 14
1 16 6
3 4 7
15 7 16
6 15 14
1 11 6
15 3 1
8 9 16
3 10 14
11 14 12
8 1 14
9 6 16
9 12 9
5 13 9
3 5 1

stdout

6
8