Üçlüklər

Verilmiş ağac, yəni dövrləri olmayan əlaqəli istiqamətsiz qraf. Hər iki zirvə üçün x, y üzərindən d(x, y) ilə x və y arasında yeganə sadə yolda olan uzunluğu (yəni kənarların sayını) ifadə edək. Bütün (sırasız) {x, y, z} üçlüklərini hesablayın ki, d(x, y) = d(y, z) = d(z, x) > 0.

Giriş məlumatları

Birinci sətir testlərin sayı z (1 ≤ z ≤ 20) ilə başlayır. Daha sonra testlərin təsvirləri gəlir.

Hər test halının birinci sətiri zirvələrin sayı n (3 ≤ n ≤ 100 000) ilə başlayır. Növbəti n - 1 sətirin hər biri iki tam ədəd a, b (1 ≤ a, b ≤ n) ehtiva edir ki, bu da zirvələr a və b arasında olan kənarı təsvir edir.

Çıxış məlumatları

Hər test üçün bir tam ədəd çıxarın: nəzərdə tutulan üçlüklərin sayı.

Nümunələr