Alice 和 Bob 在一棵有 $n$ 个顶点的树 $T$ 上玩一个游戏。Alice 想要识别出一个秘密顶点 $x$。然而，Bob 是敌对的，并且不需要预先选定 $x$。
初始时，$T$ 的每个顶点都被视为 $x$ 的“可能”候选者。每轮，Alice 选择一个顶点 $v$ 并询问从 $v$ 到 $x$ 的距离。Bob 回答一个非负整数 $d$。然后 Alice 删除所有满足 $\operatorname{dist}(u, v) \neq d$ 的候选顶点 $u$。
Bob 的回答必须与至少一个剩余的候选者一致。换句话说，在 Alice 删除所有满足 $\operatorname{dist}(u, v) \neq d$ 的顶点 $u$ 后，候选集合必须仍为非空。在此规则下，Bob 选择他的回答以迫使 Alice 使用尽可能多的询问。
一旦只剩下一个候选顶点，Alice 就获胜。Alice 选择她的询问策略以最小化询问次数。
给定树的结构，找出无论 Bob 采取何种策略，Alice 保证获胜所需的最小询问次数。
例如，如果 Alice 询问顶点 $v$ 且 Bob 回答 $d=2$，那么所有距 $v$ 恰好为 $2$ 的顶点仍为可能候选，而其他顶点均被删除。
询问 $v$ 并得到回答 2：带阴影的顶点是被询问的顶点，虚线顶点仍为可能候选，实线顶点被删除。
输入格式
第一行包含一个整数 $t$ ($1 \le t \le 10^5$)，表示测试用例的数量。
每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 2000$)，表示顶点的数量。
接下来 $n-1$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i,b_i \le n$, $a_i \ne b_i$)，表示树的一条边。
保证每个测试用例的边构成一棵树，并且所有测试用例的 $\sum n^2 \le 2000^2$。
输出格式
对于每个测试用例，输出一个整数：在最坏情况下 Alice 所需的最小询问次数。
样例
输入 1
2 4 1 2 2 3 3 4 5 1 2 1 3 1 4 1 5
输出 1
1 3
说明 1
- 在第一个测试用例中，树是一条四个顶点的路径。询问顶点 1 可能得到的距离为 0, 1, 2, 3，它们各不相同，因此一次询问就足够了。
- 在第二个测试用例中，树是以顶点 1 为中心的星形图：
- 在下图中，带阴影的顶点是被询问的顶点，虚线顶点在 Bob 回答后仍为可能候选，实线顶点已被删除。
询问 2，回答 2：顶点 3、4、5 仍为可能候选。
询问 3，回答 2：顶点 4、5 仍为可能候选。
询问 4，回答 2：只剩顶点 5。
- 这表明三次询问是足够的。Alice 首先询问叶子 2。如果 Bob 回答 0 或 1，秘密顶点立刻确定；最坏情况是回答 2，留下叶子 3、4、5。然后 Alice 询问叶子 3，最坏情况下留下叶子 4、5。最后一次询问即可区分它们。
- 两次询问是不够的。第一次询问后，Bob 可以至少保留三个叶子作为可能候选。在星形图的三个叶子中，一次距离询问无法区分全部，因为至少有两个叶子到被询问顶点的距离相同。