Трійки

Задано дерево, тобто зв'язний неорієнтований граф без циклів. Для кожної пари вершин x та y позначимо через d(x, y) довжину (тобто кількість ребер) на єдиному простому шляху між x та y. Порахуйте всі (неупорядковані) трійки {x, y, z}, для яких виконується умова d(x, y) = d(y, z) = d(z, x) > 0.

Вхідні дані

Перший рядок містить кількість тестів z (1 ≤ z ≤ 20). Далі йдуть описи тестів.

Перший рядок кожного тесту містить кількість вершин n (3 ≤ n ≤ 100 000). Кожен з наступних n - 1 рядків містить два цілих числа a, b (1 ≤ a, b ≤ n), що описують ребро між вершинами a та b.

Вихідні дані

Для кожного тесту виведіть одне ціле число: кількість знайдених трійок.

Приклади