E. 灵活的毛虫序列

时间限制：每个测试点 $2$ 秒 内存限制：每个测试点 $512$ 兆字节

无尽轮回的七日 ——r-906, Panopticon

有一棵包含 $n$ 个顶点的树。我们用整数对 $(p,q)$（满足 $1\le p,q\le n$ 且 $p\neq q$）表示一条毛虫： 它的头在顶点 $p$，尾在顶点 $q$，它支配着从 $p$ 到 $q$ 的简单路径上的所有顶点（包括 $p$ 和 $q$）。 $(p,q)$ 的毛虫序列定义为：仅由这条简单路径上的顶点组成，并按照到 $p$ 的距离升序排列得到的序列。

Nora 和 Aron 轮流移动这条毛虫，Nora 先手。 两人都采用最优策略：

• 优先让自己获胜；
• 若无法获胜，则会尽力阻止对方获胜（最终游戏平局）。

移动规则

• Nora 的回合： 必须选一个与当前头 $p$ 相邻、且不被当前毛虫支配的顶点 $u$，将整条毛虫向 $u$ 方向移动一条边。
• Aron 的回合： 必须选一个与当前尾 $q$ 相邻、且不被当前毛虫支配的顶点 $v$，将整条毛虫向 $v$ 方向移动一条边。

两人的可移动方式不同。

胜负判定

• 每当 $p$ 是叶子时，Nora 获胜。
• 每当 $q$ 是叶子时，Aron 获胜。
• 若初始时 $p,q$ 都是叶子，或游戏进行 $10^{100}$ 轮仍未结束，则结果为平局。

题目保证：只要游戏未结束，Nora 一定能选出合法的 $u$，Aron 也一定能选出合法的 $v$。

定义：

• $^*$ 更形式化地说：设当前毛虫序列为 $c_1,c_2,\dots,c_k$，移动后新序列为 $d(u,c_1),d(u,c_2),\dots,d(u,c_k)$，其中 $d(x,y)$ 表示从 $y$ 到 $x$ 的简单路径上的下一个顶点。
• $^\dagger$ 树中一个顶点是叶子当且仅当其度数为 $1$。
• $^\ddagger$ 因此只要游戏未结束，Nora 永远有合法的 $u$ 可选，Aron 同理。

---

问题

请统计满足 $1\le p,q\le n$ 且 $p\neq q$ 的整数对 $(p,q)$ 的数量，使得： 以 $(p,q)$ 作为初始毛虫时，Aron 获胜。

---

输入格式

每个测试包含多组测试数据。 第一行一个整数 $t$（$1\le t\le 2\cdot 10^4$）—— 测试数据组数。

每组测试数据：

• 第一行一个整数 $n$（$2\le n\le 2\cdot 10^5$）—— 树的顶点数。
• 接下来 $n-1$ 行，每行两个整数 $u,v$（$1\le u,v\le n$），表示 $u$ 与 $v$ 之间有一条边。
• 保证输入是一棵合法的树。

保证所有测试用例的 $n$ 之和不超过 $4\cdot 10^5$。

---

输出格式

对每组测试用例，输出一行一个整数，表示满足条件的 $(p,q)$ 对数。

---

样例输入

5
2
1 2
5
1 2
1 3
2 4
2 5
12
1 6
11 2
4 8
12 3
2 7
6 12
8 1
2 3
5 12
9 2
10 3
10
1 2
2 3
3 4
4 5
5 6
4 7
6 8
4 9
4 10
25
1 16
11 22
6 14
3 1
20 14
23 17
25 19
10 11
3 18
10 6
2 21
4 5
11 12
4 9
9 13
8 6
6 1
3 7
8 19
10 24
15 13
1 2
3 4
17 8

样例输出

0
6
40
27
171

---

样例解释

• 第一个测试用例： 所有可能毛虫为 $(1,2)$ 和 $(2,1)$。初始时 $p,q$ 都是叶子，结果均为平局，因此答案为 $0$。

• 第二个测试用例： 能让 Aron 获胜的毛虫为： $(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)$，共 $6$ 对。

  举例：

  • 毛虫 $(1,5)$：$p=1$ 不是叶子，但 $q=5$ 是叶子，因此 Aron 直接获胜。
  • 毛虫 $(2,1)$：$p=2$ 不是叶子，$q=1$ 也不是叶子。Nora 第一步可以向 $5$ 移动，毛虫变为 $(5,2)$，此时 $p=5$ 是叶子，Nora 获胜，因此该 $(p,q)$ 不计入答案。