Description

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

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

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

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

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

对于点对 $(x,y)$，如果存在一种选定根结点和执行操作的方案，使得结点 $x$ 与结点 $y$ 在同一次操作中被标记，则称二元组 $(x,y)$ 是优美的。

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

Format

Input

本题有多组测试数据。

输入的第一行包含一个整数 $T(1 \le T \le 10^5)$，表示测试数据组数。

对于每组测试数据：

第一行包含一个整数 $n(3 \le n \le 10^6)$，表示树的结点数。

接下来 $n-1$ 行，第 $i$ 行包含两个整数 $u_i,v_i(1 \leq u_i,v_i \leq 10^6)$，表示编号为 $i$ 的边连接结点 $u_i$ 和 $v_i$。

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

Output

对于每组测试数据，输出一行一个整数，表示优美点对的数量。

Samples

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
3
12
26
28
36

Note

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

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