Triples

트리가 주어진다. 트리는 사이클이 없는 연결된 무방향 그래프이다. 모든 두 정점 $x, y$에 대해 $d(x, y)$는 $x$와 $y$를 잇는 유일한 단순 경로의 길이(간선의 수)를 뜻한다. $d(x,y) = d(y,z) = d(z,x) > 0$을 만족하는 세 정점의 집합 $\{x,y,z\}$의 개수를 센다. 집합은 순서를 따지지 않는다.

첫 줄에 테스트 케이스의 개수 $z$ ($1 \leq z \leq 20$)가 주어진다. 각 테스트 케이스가 이어서 주어진다.

각 테스트 케이스의 첫 줄에는 정점의 개수 $n$ ($3 \leq n \leq 100\,000$)이 주어진다. 다음 $n-1$개 줄에는 두 정수 $a, b$ ($1 \leq a, b \leq n$)가 한 줄에 하나씩 주어지며, 정점 $a$와 $b$ 사이에 간선이 있다는 뜻이다.

각 테스트 케이스에 대해 조건을 만족하는 세 정점 집합의 개수를 정수 하나로 출력한다.