DreamGrid has just found a tree of n vertices in his backyard. As DreamGrid loves connected components, he defines an interval $[l, r]\ (1 ≤ l ≤ r ≤ n)$ as a “connected interval” if the induced subgraph formed from the set $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 $V$ of the vertices of the graph $G$ and all of the edges in graph $G$ connecting pairs of vertices in $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 ≤ n ≤ 3 × 10^5 )$ indicating the size of the tree. 

For the following $(n−1)$ lines, the $i$-th line contains two integers $a_i,b_i\ (1 ≤ a_i , b_i ≤ 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×10^5$.

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