C. Super Pair
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You will be given a tree containing $$$n$$$ nodes. An unordered pair $$$(u,v)$$$ is called a Super Pair if it satisfies the following conditions:

  1. $$$u≠v$$$;
  2. Initially, there will be no edge between node $$$u$$$ and node $$$v$$$;
  3. If we add an edge between $$$u$$$ and $$$v$$$, there will be exactly one shortest path between every pair of nodes. Note that we don't add this edge in the tree actually.

Your task is to calculate the number of Super Pairs.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^{4}$$$). The description of the test cases follows.

The first line of each testcase contains a single integer $$$n$$$ $$$(2 \le n \le 10^{5})$$$ — the number of nodes in the given tree.

The next $$$n-1$$$ lines contain two integers $$$u,v$$$ $$$(1 \le u,v \le n, u≠v)$$$ — there is an edge connecting $$$u$$$ and $$$v$$$.

It is guaranteed that the sum of $$$n$$$ over all testcases doesn't exceed $$$10^{5}$$$.

Output

For each testcase, print a single integer — the number of Super Pairs.

Example
Input
3
2
2 1
4
1 2
3 1
1 4
6
1 2
1 3
1 4
4 5
5 6
Output
0
3
7