题目描述

给定一棵有 $N$ 个顶点的树。树上的某一个顶点中有一枚棋子。

你拥有 $K$ 门炮，可以进行一系列操作。每次操作中，每门炮都可以向你选择的一个顶点开火。也就是说，每次操作你会击中树上的 $K$ 个顶点。

在你的两次操作之间，棋子可以选择：

• 移动到当前所在顶点的一个相邻顶点；
• 或者留在原地不动。

每次操作后，树本身不会发生变化。

你在任何时刻都不知道棋子的具体位置。

请编写程序 artillery，求最小的 $K$，使得你一定能够保证在某一次操作中击中这枚棋子。

输入格式

第一行输入一个整数 $T$，表示子测试数量。

对于每个子测试：

第一行输入一个整数 $N$，表示树的顶点数。

接下来 $N-1$ 行，每行输入两个整数，描述树中的一条边。每条边由它连接的两个顶点给出。

顶点编号从 0 开始。

输出格式

输出 $T$ 行。

第 $i$ 行输出第 $i$ 个子测试所需的最小 $K$。

数据范围

子任务：

• 40% 的测试：$N \le 1000$；
• 另外 30% 的测试：$N \le 10000$。

评分方式

设 $a_1,a_2,\ldots,a_T$ 是各子测试的正确答案，$b_1,b_2,\ldots,b_T$ 是你的程序输出的答案。

第 $i$ 个子测试的得分为：

• 若 $a_i=b_i$，得分为 1.0；
• 若 $a_i=b_i-1$，得分为 0.7；
• 其他情况得分为 0。

一个测试点的最终得分等于所有子测试得分的乘积，再乘以该测试点的满分。

样例

输入

2
8
0 1
0 2
0 3
1 4
2 5
3 6
3 7
9
0 1
0 2
0 3
1 4
1 5
1 6
3 7
3 8

输出

3
2

样例解释

在第一个子测试中，可以用 $3$ 门炮保证消灭棋子。可以采用如下操作序列：

第 1 次操作：击中顶点 0, 1, 4；

第 2 次操作：击中顶点 0, 2, 5；

第 3 次操作：击中顶点 0, 3, 6；

第 4 次操作：击中顶点 0, 3, 7。

采用这些操作时，无论棋子如何移动，它最终都会被击中。

如果炮的数量少于 $3$，则棋子总有办法躲避，使自己不被击中。