题目描述

给定一棵包含 $n$ 个结点的无根树。

初始时，你需要确定一个结点为根；接下来，你可以进行任意次操作。

每次操作，你需要依次执行下面的步骤：

• 选择一个正整数 $k$。
• 标记当前每一棵树中到其根距离为 $k$ 的结点，删掉这些结点与其父亲的连边，形成若干棵新树。
• 令这些被标记的结点为对应新树的根。

其中，点 $u$ 到点 $v$ 的距离等于两点之间简单路径上边的数量。

对于点对 $(x,y)$，如果有一种钦定根与操作的方案，能使得结点 $x$ 与结点 $y$ 在同一次操作中被标记，我们称该二元组是优美的。

你需要求出满足 $1\le x\lt y\le n$ 的点对 $(x,y)$ 中，有多少个点对是优美的。

输入格式

本题有多组测试数据。

输入的第一行一个整数 $T$ 表示测试数据组数（$1\le T\le 10^5$）。

对于每组测试数据，

• 第一行包含一个整数 $n$（$3\le n\le 10^6$）。
• 接下来 $n−1$ 行，第 $i$ 行包含两个整数 $u_i,v_i$，表示树上编号为 $i$ 的边连接结点 $u_i$ 和 $v_i$。

保证给出的所有边构成一棵树；保证对于单个测试点，所有 $n$ 的和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行一个整数表示答案。

样例

输入样例 1

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

输出样例 1

1
3
12
26
28
36

样例解释

对于第一组数据，优美的点对只有 $(1,3)$。

对于第二组数据，优美的点对有 $(1,3)$、$(1,4)$ 和 $(3,4)$。