One day, a giant tree grew in the countryside. Little John, with his childhood eagle, decided to make it his home. Little John will build a structure on the tree with galvanized square steel. However, little did he know, he could not build what is physically impossible.

You are given a rooted tree$$$^{\text{∗}}$$$ containing $$$n$$$ vertices rooted at vertex $$$1$$$. A pair of vertices $$$(u,v)$$$ is called a good pair if $$$u$$$ is not an ancestor$$$^{\text{†}}$$$ of $$$v$$$ and $$$v$$$ is not an ancestor of $$$u$$$. For any two vertices, $$$\text{dist}(u,v)$$$ is defined as the number of edges on the unique simple path from $$$u$$$ to $$$v$$$, and $$$\text{lca}(u,v)$$$ is defined as their lowest common ancestor.

A function $$$f(u,v)$$$ is defined as follows.

If $$$(u,v)$$$ is a good pair, $$$f(u,v)$$$ is the number of distinct integer values $$$x$$$ such that there exists a non-degenerate triangle$$$^{\text{‡}}$$$ formed by side lengths $$$\text{dist}(u,\text{lca}(u,v))$$$, $$$\text{dist}(v,\text{lca}(u,v))$$$, and $$$x$$$.
Otherwise, $$$f(u,v)$$$ is $$$0$$$.

You need to find the following value: $$$$$$\sum_{i = 1}^{n-1} \sum_{j = i+1}^n f(i,j).$$$$$$

$$$^{\text{∗}}$$$A tree is a connected graph without cycles. A rooted tree is a tree where one vertex is special and called the root.

$$$^{\text{†}}$$$An ancestor of vertex $$$v$$$ is any vertex on the simple path from $$$v$$$ to the root, including the root, but not including $$$v$$$. The root has no ancestors.

$$$^{\text{‡}}$$$A triangle with side lengths $$$a$$$, $$$b$$$, $$$c$$$ is non-degenerate when $$$a+b \gt c$$$, $$$a+c \gt b$$$, $$$b+c \gt a$$$.

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 test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$).

Each of the next $$$n-1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$, denoting the two vertices connected by an edge ($$$1 \le u_i,v_i \le n$$$, $$$u_i \neq v_i$$$).

It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, output the answer on a separate line.

Note

On the first test case, the only good pair $$$(i,j)$$$ satisfying $$$i \lt j$$$ is $$$(2,3)$$$. Here, $$$\text{lca}(2,3)$$$ is $$$1$$$, and the two distances are $$$1$$$ and $$$1$$$.

There is only one value of $$$x$$$ for two side lengths $$$1$$$ and $$$1$$$, which is $$$1$$$. Therefore, the answer for the first test case is $$$1$$$.

On the second test case, there is no good pair. Therefore, the answer for the second test case is $$$0$$$.

On the third test case, the good pairs $$$(i,j)$$$ satisfying $$$i \lt j$$$ are as follows.

$$$(2,5)$$$: $$$\text{lca}(2,5)$$$ is $$$1$$$, distances are $$$1$$$ and $$$1$$$. There is only one possible value of $$$x$$$, which is $$$1$$$.
$$$(3,4)$$$: $$$\text{lca}(3,4)$$$ is $$$2$$$, distances are $$$1$$$ and $$$1$$$. There is only one possible value of $$$x$$$, which is $$$1$$$.
$$$(3,5)$$$: $$$\text{lca}(3,5)$$$ is $$$1$$$, distances are $$$2$$$ and $$$1$$$. There is only one possible value of $$$x$$$, which is $$$2$$$.
$$$(4,5)$$$: $$$\text{lca}(4,5)$$$ is $$$1$$$, distances are $$$2$$$ and $$$1$$$. There is only one possible value of $$$x$$$, which is $$$2$$$.

Therefore, the answer for the third test case is $$$1+1+1+1=4$$$.

Triangle Tree

Examples