You are given a tree with vertices numbered from to . The distance between two vertices is the number of edges on the simple path between them.
A non-empty set of vertices is called connected if for every two vertices of all vertices of the simple path between them also belong to .
For every from to , find the maximum size of a connected set such that the distance between any two vertices of is at most .
The first line contains a single integer (1 \le t \le 5000) — the number of test cases.
The first line of each test case contains an integer (1 \le n \le 5000) — the number of vertices. Each of the next n - 1 lines contains two integers and (1 \le u, v \le n, u \ne v) — an edge between vertices and . It is guaranteed that the edges form a tree.
The sum of over all test cases does not exceed .
For each test case print one line with integers: the -th of them must be the maximum size of a connected set of vertices in which the distance between any two vertices is at most .
Example 1
In the first test case the tree has vertices: vertex is adjacent to , and , and vertex is adjacent to , and .
For x = 1 the answer is , for example S = \{1, 3\}.
For x = 2 the answer is , for example S = \{1, 3, 4, 5\}.
For x = 3 the answer is , for example S = \{1, 3, 4, 5, 7\}: the largest distances are between and and between and , and they are equal to .
For x \ge 4 the answer is , since the set of all vertices has largest distance .
In the second test case the tree consists of a single vertex, so the answer is .
In the third test case the tree is the chain 1 - 2 - 3 - 4. A connected set of vertices of a chain has largest distance k - 1, so the answers for x = 1, 2, 3, 4 are 2, 3, 4, 4.