DreamGrid has just found a tree of vertices in his backyard. As DreamGrid loves connected components, he defines an interval () as a connected interval if the induced subgraph formed from the set consists of exactly one connected component, where indicates the vertex whose index is .
Given the tree in DreamGrid's backyard, your task is to help DreamGrid count the number of connected intervals.
Recall that an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges in graph connecting pairs of vertices in .
输入格式
There are multiple test cases. The first line of the input contains an integer indicating the number of test cases. For each test case:
The first line contains an integer () indicating the size of the tree.
For the following lines, the -th line contains two integers and () indicating that there is an edge connecting vertex and vertex in the tree.
It's guaranteed that the given graph is a tree and that the sum of in all test cases will not exceed .
输出格式
For each test case output one line containing one integer, indicating the number of connected intervals.
样例
样例输入 1
2
4
1 2
2 3
3 4
4
1 2
2 3
2 4
样例输出 1
10
9
数据范围与提示
For the first sample test case, all intervals are connected intervals.
For the second sample test case, all intervals but are connected intervals.
