* $x y 0$ insemnand ca $y$ este fiul stang al lui $x$
* $x y 1$ insemnand ca $y$ este fiul drept al lui $x$

Doi brazi sunt asemenea daca, schimband etichetarea unuia dintre ei, se obtin fix muchiile celuilalt.

Doi brazi sunt asemenea, daca

De exemplu: bradul 1 2 0, 1 3 1, 2 4 0 nu este asemenea cu bradul 1 2 1, 1 3 0, 2 4 1 dar este asemenea cu 1 3 0, 1 2 1, 3 4 0.

De exemplu: bradul 1 2 0, 1 3 1, 2 4 0 nu este asemenea cu bradul 1 2 1, 1 3 0, 1 4 2 dar este asemenea cu 1 3 0, 1 2 1, 3 4 0.

Se dau $T$ astfel de brazi care contin maxim 10 noduri. Pentru fiecare brad i, sa se afiseze numarul de brazi din primii $i-1$ care sunt asemenea cu el.

* $1 ≤ T ≤ 100000$
* $1 ≤ N ≤ 10$

* $1 ≤ x, y ≤ N$

h2. Exemplu

4
1 2 1
1 3 0

2 4 1

1 4 2

4
1 3 0
1 2 1

9419