Nanatsukaze - Aria

You are given a tree of $$$n$$$ vertices. We define the value of a pair $$$(u,v)$$$ ($$$1\leq u\leq v\leq n$$$) as the size of the largest component after removing all edges on the path from $$$u$$$ to $$$v$$$ in the original tree.

For every $$$1\leq i\leq n$$$, you have to find the number of pairs $$$(u,v)$$$ satisfying that its value is $$$i$$$.

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\leq n \leq 10^5$$$) — the number of vertices.

Then $$$n-1$$$ lines follow, the $$$i$$$-th line containing two integers $$$u$$$ and $$$v$$$ ($$$1\leq u,v\leq n$$$) — the two vertices that the $$$i$$$-th edge connects.

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 $$$5\cdot 10^5$$$.

Output

For each test case, output $$$n$$$ integers, the $$$i$$$-th of which denotes the number of distinct pairs $$$(u,v)$$$ satisfying its value is $$$i$$$.

Note

In the first test case, the value of pair $$$(1, 1)$$$ is $$$1$$$.

In the second test case, the values of pairs $$$(1, 1)$$$ and $$$(2, 2)$$$ are both $$$2$$$, because no edges will be removed. The value of pair $$$(1, 2)$$$ is $$$1$$$, because edge $$$(1, 2)$$$ is on the path from $$$1$$$ to $$$2$$$ in the tree, and after removing it, there will be $$$2$$$ components left, which are $$$\{1\}$$$ and $$$\{2\}$$$, and the size of the largest component is $$$1$$$.

In the sixth test case, the value of pair $$$(4, 6)$$$ is $$$3$$$, because edges $$$(3, 4)$$$, $$$(2, 3)$$$, and $$$(2, 6)$$$ are on the path from $$$4$$$ to $$$6$$$ in the tree, and after removing them, there will be $$$4$$$ components left, which are $$$\{1, 2, 5\}$$$, $$$\{3, 7\}$$$, $$$\{4\}$$$, and $$$\{6\}$$$, and the size of the largest component is $$$3$$$.

Statistics on Tree

Examples