题目描述

DreamGrid has just found a tree of $n$ vertices in his backyard. As DreamGrid loves connected components, he defines an interval $[l, r]$ ($1 \le l \le r \le n$) as a connected interval if the induced subgraph formed from the set $\mathbb{V} = \{v_i | i \in [l, r]\}$ consists of exactly one connected component, where $v_i$ indicates the vertex whose index is $i$.

Given the tree in DreamGrid's backyard, your task is to help DreamGrid count the number of connected intervals.

Recall that an induced subgraph $G'$ of a graph $G$ is another graph, formed from a subset $\mathbb{V}$ of the vertices of the graph $G$ and all of the edges in graph $G$ connecting pairs of vertices in $\mathbb{V}$.

输入格式

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 3 \times 10^5$) indicating the size of the tree.

For the following $(n-1)$ lines, the $i$-th line contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$) indicating that there is an edge connecting vertex $a_i$ and vertex $b_i$ in the tree.

It's guaranteed that the given graph is a tree and that the sum of $n$ in all test cases will not exceed $3 \times 10^5$.

输出格式

For each test case output one line containing one integer, indicating the number of connected intervals.

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

10
9

提示

For the first sample test case, all intervals are connected intervals.

For the second sample test case, all intervals but $[3, 4]$ are connected intervals.