Triples#9109
You are given a tree, which is a connected undirected graph without cycles. For any two vertices and , let d(x, y) denote the length (i.e., the number of edges) on the unique simple path between and . Count the number of all (unordered) triples \{x, y, z\} such that d(x, y) = d(y, z) = d(z, x) > 0.
The first line contains the number of test cases z~(1 \le z \le 20). Then follow the descriptions of the test cases.
The first line of each test case contains a single integer n~(3 \le n \le 10^5) — the number of vertices. Each of the next n - 1 lines contains two integers and b~(1 \le a, b \le n), representing an edge between vertices and .
For each test case, print a single integer — the number of such triples.
Example 1