• For Solution

This version of the problem differs from the next one only in the constraint on nn.

A tree is a connected undirected graph without cycles. A weighted tree has a weight assigned to each edge. The distance between two vertices is the minimum sum of weights on the path connecting them.

You are given a weighted tree with nn vertices, each edge has a weight of 11. Denote d(v)d(v) as the distance between vertex 11 and vertex vv.

Let f(x)f(x) be the minimum possible value of max1vn d(v)max1≤v≤n d(v) if you can temporarily add an edge with weight xx between any two vertices aa and bb (1a,bn)(1≤a,b≤n). Note that after this operation, the graph is no longer a tree.

For each integer xx from 11 to nn, find f(x)f(x).

Input Distance Tree (easy version) solution codeforces

The first line co ntains a single integer tt (1t1041≤t≤104) — the number of test cases.

The first line of each test case contains a single integer nn (2n30002≤n≤3000).

Each of the next n1n−1 lines contains two integers uu and vv (1u,vn1≤u,v≤n) indicating that there is an edge between vertices uu and vv. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of nn over all test cases doesn’t exceed 30003000.

Output Distance Tree (easy version) solution codeforces

For each test case, print nn integers in a single line, xx-th of which is equal to f(x)f(x) for all xx from 11 to nn.

Example

input

Copy
3
4
1 2
2 3
1 4
2
1 2
7
1 2
1 3
3 4
3 5
3 6
5 7


output Distance Tree (easy version) solution codeforces

Copy
1 2 2 2
1 1
2 2 3 3 3 3 3

Note

In the first testcase:

• For x=1x=1, we can an edge between vertices 11 and 33, then d(1)=0d(1)=0 and d(2)=d(3)=d(4)=1d(2)=d(3)=d(4)=1, so f(1)=1f(1)=1.
• For x2x≥2, no matter which edge we add, d(1)=0d(1)=0d(2)=d(4)=1d(2)=d(4)=1 and d(3)=2d(3)=2, so f(x)=2f(x)=2.