DreamGrid 在他的后院里发现了一棵有 $n$ 个顶点的树。由于 DreamGrid 热爱连通分量，他将一个区间 $[l, r]$ ($1 \le l \le r \le n$) 定义为“连通区间”，如果由集合 $\mathbb{V} = \{v_i \mid i \in [l, r]\}$ 诱导出的子图恰好由一个连通分量组成，其中 $v_i$ 表示索引为 $i$ 的顶点。

给定 DreamGrid 后院里的这棵树，你的任务是帮助 DreamGrid 计算连通区间的数量。

回想一下，图 $G$ 的诱导子图 $G'$ 是由图 $G$ 的顶点集合的一个子集 $\mathbb{V}$ 以及图 $G$ 中所有连接 $\mathbb{V}$ 中顶点对的边所组成的图。

输入格式

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

第一行包含一个整数 $n$ ($1 \le n \le 3 \times 10^5$)，表示树的大小。

接下来的 $(n-1)$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le n$)，表示树中存在一条连接顶点 $a_i$ 和顶点 $b_i$ 的边。

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

输出格式

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

样例

输入 1

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

输出 1

10
9

说明

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

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