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

Входные данные

Первая строка содержит количество тестов z (1 ≤ z ≤ 20). Далее следуют описания тестов.

The first line of every test case contains the number of vertices n (3 ≤ n ≤ 100 000). Каждая из следующих n - 1 строк содержит два целых числа a, b (1 ≤ a, b ≤ n), описывающих ребро между вершинами a и b.

Выходные данные

Для каждого теста выведите одно целое число: количество рассматриваемых троек.