Rikka with Travels

Problem Description

To enjoy their summer vacations, Rikka and Yuta decide to go travels. According to past experiences, contradictions always arose when they were planning for the same trip. This time, they decide to make plans dividually and will go travel twice. Coincidentally, they choose the same country Fantasy as the destination, which is a small island country on the Pacific. There are $n$ cities in Fantasy and they are connected with $n-1$ two-way roads. It is guaranteed that any two cities can reach each other by the road system. Though Rikka and Yuta love travels, visiting the same city more than once is still boring for them. Therefore, both Rikka and Yuta choose a simple path (i.e., a path without visiting any city more than once) as her/his plan. Moreover, they want to ensure the two paths do not intersect on any city. Suppose Rikka chooses the path from $a$ to $b$, Yuta chooses the path from $c$ to $d$ (both $a=b$ and $c=d$ are allowed), they define the feature of the plan is an ordered pair $(L(a,b),L(c,d))$, where $L(x,y)$ represents the number of cities on the path from $x$ to $y$. Now, Rikka wants to count the number of different features, i.e., the number of different integer pairs $(l_1,l_2)$ which satisfies there exists a valid travel plan $(a,b,c,d)$ meets $L(a,b) = l_1, L(c,d) = l_2$. Since Rikka and Yuta are busy with planning their trip, Rikka asks you to help her calculate the answer.

Input

The first line of the input contains a single integer $T(1 \leq T \leq 300)$, the number of test cases. For each test case, the first line contains a single integer $n(1 \leq n \leq 10^5)$, the number of cities in Fantasy. Then $n-1$ lines follow. Each line contains two integers $u_i,v_i(1 \leq u_i,v_i \leq n)$ which represents a two-way road $(u_i,v_i)$ in the road system. The input guarantees that there are no more than $5$ test cases with $n > 500$.

Output

For each test case, output a single line with a single integer, the answer. Hint In the first test case, the possible features are $(1,1), (1,2), (1,3), (2,1), (3,1)$. Therefore the answer is $5$. In the second test case, the possible features are $(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(3,1),(3,2), (4,1)$. Therefore the answer is $10$.

Sample Input

2

4

1 2

1 3

1 4

5

1 2

2 3

3 4

3 5

Sample Output

5

10

Source

2019 Multi-University Training Contest 9