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 會最佳化選擇她的詢問，以最小化詢問次數。
給定樹的結構，找出 Alice 無論 Bob 的策略如何，都能保證獲勝所需的最少詢問次數。
例如，如果 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 可以讓至少三個葉子仍為可能。在星形的三個葉子中，再多一次距離詢問無法區分所有葉子，因為至少有兩個葉子到被詢問頂點的距離相同。