Given a tree with $n$ vertices, you need to assign a color to each edge. Define the inconvenience of an assignment as the maximum number of colors on the path between any two vertices.

You need to assign exactly $k$ different colors (each color must appear at least once) to the edges while minimizing the inconvenience of the assignment.

Please calculate the minimum inconvenience for all $k=1,2,\ldots,n-1$.

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 the input contains one positive integer $n$ ($3\le n\le3\cdot10^5$) — the number of vertices.

The next $n-1$ lines each contain two positive integers $u_i,v_i$ ($1\le u_i,v_i\le n$) — indicating that there is an edge between vertices $u_i$ and $v_i$.

It is guaranteed that the edges in the input form a tree.

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

Output

For each test case, print a single line containing $n-1$ integers. The $i$-th integer represents the minimum inconvenience for $k=i$.

Note

In the first test case, possible solutions for $k=1,2,\ldots,n-1$ are as follows: