Description

DreamGrid 刚刚在自家后院发现了一棵有 $n$ 个节点的树。由于 DreamGrid 喜欢连通块，他将区间 $[l, r]$（$1 \le l \le r \le n$）定义为“连通区间”，当且仅当由集合 $\mathbb{V} = \{v_i | i \in [l, r]\}$ 所形成的诱导子图正好有且只有一个连通块，其中 $v_i$ 表示编号为 $i$ 的节点。

给定 DreamGrid 后院里的这棵树，请你帮他统计有多少个连通区间。

回忆一下，图 $G$ 的诱导子图 $G'$ 是这样一个图：它由 $G$ 的部分顶点子集 $\mathbb{V}$ 以及所有连接 $\mathbb{V}$ 内任意两点的边组成。

Input Format

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对每组测试数据：

第一行包含一个整数 $n$（$1 \le n \le 3 \times 10^5$），表示树的节点数。

接下来的 $(n - 1)$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$），表示节点 $a_i$ 和 $b_i$ 之间有一条边。

保证输入图为一棵树，且所有测试数据中 $n$ 的总和不超过 $3 \times 10^5$。

Output Format

对于每组测试数据输出一行一个整数，表示连通区间的数量。

2
4
1 2
2 3
3 4
4
1 2
2 3
2 4

10
9

Hint

对于第一个样例测试，所有区间都是连通区间。

对于第二个样例测试，除了 $[3, 4]$ 之外，所有区间都是连通区间。

由 ChatGPT 5 翻译