题目描述

你有一棵 $n$ 个点，$n-1$ 条边的无根树，但是树没有根是活不了的，所以你需要给树找一个根。有了根之后，每个点到根的距离都可以算出来（每条边的长度为 1，根到根的距离为 0），那么你就可以得到一个长度为 $n$ 的序列 $a$。为了尽可能地使得每个点均匀地吸收养分，你想要让这个序列的方差尽可能的小！

为了确保答案是一个整数，请你输出方差乘以 $n^2$ 的结果。具体来说，假设这个序列的平均值为 $x$，你需要输出的是：

输入格式

第一行输入一个正整数 $t(1 \leq t \leq 5)$，表示共有 $t$ 组数据。

每组数据的第一行输入一个正整数 $n$ ，接下来包含 $n-1$ 行。

每行给出两个正整数 $a,b$，表示 $a,b$ 之间有一条边。

输出格式

输出 $t$ 行，每行一个整数表示结果。

样例

1
4
1 2
1 3
1 4

3

【说明】

选择 1 作为根，则 1、2、3、4 这四个点到根的距离分别为 [0,1,1,1]，这个数组的平均值为 0.75，计算 $4*((0-0.75)^2+(1-0.75)^2+(1-0.75)^2+(1-0.75)^2)=3$

1
4
1 2
1 3
3 4

8

【说明】

选择 1 作为根，则四个点到根的距离分别为 [0,1,1,2]，平均值为 1，计算 $4*((0-1)^2+(1-1)^2+(1-1)^2+(2-1)^2)=8$

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

8
81

数据范围与提示

本题共 10 个测试点：

对于 1 测试点，有 $1 \leq n \leq 100$

对于 2-3 测试点，有 $1 \leq n \leq 1000$

对于 4-5 测试点，这棵树是一条链

对于所有测试点，有 $1 \leq n \leq 40000,1 \leq t \leq 5,1≤t≤5$