Задано дерево з вершинами, пронумерованими від до . Відстанню між двома вершинами називається кількість ребер на простому шляху між ними.
Непорожня множина вершин називається зв'язною, якщо для будь-яких двох вершин з усі вершини простого шляху між ними також належать .
Для кожного від до знайдіть найбільший розмір зв'язної множини такої, що відстань між будь-якими двома вершинами з не перевищує .
Перший рядок містить одне ціле число (1 \le t \le 5000) — кількість тестових випадків.
Перший рядок кожного тестового випадку містить ціле число (1 \le n \le 5000) — кількість вершин. Кожен із наступних n - 1 рядків містить два цілі числа та (1 \le u, v \le n, u \ne v) — ребро між вершинами і . Гарантується, що ребра утворюють дерево.
Сума за всіма тестовими випадками не перевищує .
Для кожного тестового випадку виведіть один рядок з цілими числами: -те з них має дорівнювати найбільшому розміру зв'язної множини вершин, у якій відстань між будь-якими двома вершинами не перевищує .
Приклад 1
У першому тестовому випадку дерево має вершин: вершина суміжна з , і , а вершина — з , і .
Для x = 1 відповідь — , наприклад S = \{1, 3\}.
Для x = 2 відповідь — , наприклад S = \{1, 3, 4, 5\}.
Для x = 3 відповідь — , наприклад S = \{1, 3, 4, 5, 7\}: найбільші відстані — між і та між і , і вони дорівнюють .
Для x \ge 4 відповідь — , оскільки для множини всіх вершин найбільша відстань дорівнює .
У другому тестовому випадку дерево складається з однієї вершини, тому відповідь — .
У третьому тестовому випадку дерево — це ланцюжок 1 - 2 - 3 - 4. Для зв'язної множини з вершин ланцюжка найбільша відстань дорівнює k - 1, тому відповіді для x = 1, 2, 3, 4 — це 2, 3, 4, 4.