Thanos. Equilibrador d’universos, terror de la vida, i 3 vegades guanyador del torneig interestelar “Cara més semblant a una pruna”. Aquest ets tu. I estas obsessionat amb el nombre 2. Especialment dividir per 2, però això es un Spoiler. Et dediques a anar per tots els planetes de l’univers massacrant a la meitat de la gent de cada planeta, per deixar-ho tot perfectament equilibrat. Després marxes a un altre planeta mitjançant salts a la velocitat de la llum. T’agradaria que cada viatge entre dos planetes contingués exactament dos salts, perquè així son salts perfectament equilibrats, però al mateix temps que els viatges fossin òptims, perquè no vols perdre temps per a massacrar més gent. Es considera un viatge òptim entre a i b si és el viatge més curt que es pot fer (passant per menys planetes)

Entrada

La primera línea es el nombre de casos de prova. Cada cas conté: En la primera linea un nombre n que significa el nombre de planetes que hi ha en aquella galaxia, entre 1 i 1 milio. Després hi haura n-1 linies, amb les vies d’hiperespai que connecten els planetes. Cada via es considera un salt

Sortida

Per cada cas de prova hauràs d’escriure el nombre de viatges òptims que tenen una longitud exacta de dos salts.

Exemple d'Entrada

4
3
1 2
1 3
5
2 1
1 5
3 1
4 3
10
1 2
2 3
2 4
1 5
3 6
2 7
7 8
5 9
5 10
8
1 2
2 3
3 4
4 5
5 6
6 1
2 1

Exemple de Sortida

2
8
24
12

Explicació del primer cas de proves

Hi ha dos camins òptims de longitud dos, 2 -> 1 -> 3 i 3 -> 1 -> 2 1 -> 2 -> 1 també té longitud dos, però hi ha un camí més òptim entre 1 i 1, en aquest cas, de longitud 0.