Problem: codeforces/2063E
Time limit: 2000 ms, Memory limit: 256 MB

One day, a giant tree grew in the countryside. Little John, with his childhood eagle, decided to make it his home. Little John will build a structure on the tree with galvanized square steel. However, little did he know, he could not build what is physically impossible.You are given a rooted tree $ ^{\text{∗}} $ containing $ n $ vertices rooted at vertex $ 1 $ . A pair of vertices $ (u,v) $ is called a good pair if $ u $ is not an ancestor $ ^{\text{†}} $ of $ v $ and $ v $ is not an ancestor of $ u $ . For any two vertices, $ \text{dist}(u,v) $ is defined as the number of edges on the unique simple path from $ u $ to $ v $ , and $ \text{lca}(u,v) $ is defined as their [lowest common ancestor](https://en.wikipedia.org/wiki/Lowest_common_ancestor).

A function $ f(u,v) $ is defined as follows.

- If $ (u,v) $ is a good pair, $ f(u,v) $ is the number of distinct integer values $ x $ such that there exists a non-degenerate triangle $ ^{\text{‡}} $ formed by side lengths $ \text{dist}(u,\text{lca}(u,v)) $ , $ \text{dist}(v,\text{lca}(u,v)) $ , and $ x $ .
- Otherwise, $ f(u,v) $ is $ 0 $ .

You need to find the following value: $$\sum_{i = 1}^{n-1} \sum_{j = i+1}^n f(i,j). $$ 

$^{\text{∗}} $ A tree is a connected graph without cycles.  A rooted tree is a tree where one vertex is special and called the root.

$ ^{\text{†}} $ An ancestor of vertex  $ v $  is any vertex on the simple path from  $ v $  to the root, including the root, but not including  $ v $ . The root has no ancestors. 

$ ^{\text{‡}} $ A triangle with side lengths  $ a $ ,  $ b $ ,  $ c $  is non-degenerate when  $ a+b \gt c $ ,  $ a+c \gt b $ ,  $ b+c \gt a$.

Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 3 \cdot 10^5 $ ).

Each of the next $ n-1 $ lines contains two integers $ u_i $ and $ v_i $ , denoting the two vertices connected by an edge ( $ 1 \le u_i,v_i \le n $ , $ u_i \neq v_i $ ).

It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 3 \cdot 10^5 $ .

Output Format

For each test case, output the answer on a separate line.


Sample Input 1

```
4
3
1 2
1 3
3
1 2
3 2
5
2 3
1 5
4 2
1 2
11
2 1
2 3
2 4
4 5
6 5
5 7
4 8
8 9
7 10
10 11
```

Sample Output 1

```
1
0
4
29
```

Notes

On the first test case, the only good pair $ (i,j) $ satisfying $ i<j $ is $ (2,3) $ . Here, $ \text{lca}(2,3) $ is $ 1 $ , and the two distances are $ 1 $ and $ 1 $ .

There is only one value of $ x $ for two side lengths $ 1 $ and $ 1 $ , which is $ 1 $ . Therefore, the answer for the first test case is $ 1 $ .

On the second test case, there is no good pair. Therefore, the answer for the second test case is $ 0 $ .

On the third test case, the good pairs $ (i,j) $ satisfying $ i<j $ are as follows.

- $ (2,5) $ : $ \text{lca}(2,5) $ is $ 1 $ , distances are $ 1 $ and $ 1 $ . There is only one possible value of $ x $ , which is $ 1 $ .
- $ (3,4) $ : $ \text{lca}(3,4) $ is $ 2 $ , distances are $ 1 $ and $ 1 $ . There is only one possible value of $ x $ , which is $ 1 $ .
- $ (3,5) $ : $ \text{lca}(3,5) $ is $ 1 $ , distances are $ 2 $ and $ 1 $ . There is only one possible value of $ x $ , which is $ 2 $ .
- $ (4,5) $ : $ \text{lca}(4,5) $ is $ 1 $ , distances are $ 2 $ and $ 1 $ . There is only one possible value of $ x $ , which is $ 2 $ .

Therefore, the answer for the third test case is $ 1+1+1+1=4 $ .