Grouped Vertices#13108

Grouped Vertices

3 seconds
256 megabytes

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 .

Input

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 .

Output

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 .

Examples

Example 1

Loading
Loading

Note

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.