Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4121
Connected Intervals

Time Limit: 2 Seconds      Memory Limit: 131072 KB

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}$.

Input

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$.

Output

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

Sample Input

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

Sample Output

10
9

Hint

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.


Author: LIN, Xi
Source: The 10th Shandong Provincial Collegiate Programming Contest
Submit    Status