I. Connected Intervals
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Example
Input
2
4
1 2
2 3
3 4
4
1 2
2 3
2 4
Output
10
9
Note

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.