Oh, No!!! Not another one of these.

You are given a tree with N vertices. Each vertex is represented by a unique integer from 1 to N. The simple path between two different vertices $[(u, v), u < v]$ is good if the sequence created by listing the vertices on the path from u to v follows the following properties.

• The path has $2k+1$ vertices where $k$ is a positive integer.
• Assuming the sequence of the vertices on the path is $h_1=u, h_2, ... ,h_{2k+1}=v$ then the path satisfies the condition $h_1 < h_2 < ... < h_k < h_{k+1} > h_{k+2} > ... > h_{2k} > h_{2k+1}$.

So, how many different pairs of vertices $[(u, v), u < v]$ are in the tree with a good simple path between them? Please note that the simple path is also the shortest path between two vertices.

The first line of the input contains an integer T denoting the number of test cases. Each test starts with an integer N (2 ≤ N ≤ 10⁵), the size of the tree. The next N-1 line each contains two integers a and b (1 ≤ a, b ≤ N, a != b), representing an edge of the tree connecting the vertices a and b. It is guaranteed that $\sum$N ≤ 2×10⁵ over all test cases and the input forms a valid connected tree.

Input file is large. Please be sure to use faster input/output methods.

For each test case print one integer, the number of different pairs of vertices [(u, v), u < v] with a good simple path in the tree.

Contest: NCPC 2023 Onsite Hosted by JU

Problem setter: Nafis Sadique