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 の答えは、少なくとも 1 つの残っている候補と矛盾してはならない。言い換えると、Alice が $\operatorname{dist}(u, v) \neq d$ である頂点 $u$ をすべて削除した後も、候補集合は空であってはならない。このルールの下で、Bob は Alice ができるだけ多くの質問を使うように答えを選ぶ。

Alice はちょうど 1 つの候補頂点が残った時点で勝利する。Alice は質問回数を最小化するように最適に質問を選ぶ。

木の構造が与えられたとき、Bob の戦略によらず、Alice が勝利を保証するために必要な最小の質問回数を求めよ。

例えば、Alice が頂点 $v$ を質問し、Bob が $d=2$ と答えた場合、$v$ から距離がちょうど $2$ のすべての頂点が候補として残り、それ以外の頂点は削除される。

$v$ を質問して答え $2$ を受け取った場合：ハッチングされた頂点が質問された頂点、点線の頂点が可能性のある頂点、無地の頂点は削除される。

入力

最初の行には 1 つの整数 $t$ ($1 \le t \le 10^5$) が含まれ、テストケースの数を表す。

各テストケースは 1 つの整数 $n$ ($2 \le n \le 2000$) で始まり、頂点数を表す。

続く $n-1$ 行のそれぞれには 2 つの整数 $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 行に出力せよ。

入出力例

入力 1

2
4
1 2
2 3
3 4
5
1 2
1 3
1 4
1 5

出力 1

1
3

注記 1

• 最初のテストケースでは、木は 4 頂点のパスである。頂点 1 を質問すると、可能性のある距離は 0, 1, 2, 3 で全て異なるため、1 回の質問で十分である。
• 2 番目のテストケースでは、木は頂点 1 を中心とするスターである。
• 以下の図では、ハッチングされた頂点が質問された頂点、点線の頂点が Bob の答えの後に残る可能性のある頂点、無地の頂点は削除された頂点である。

頂点 2 を質問して答え 2：頂点 3, 4, 5 が可能性のある頂点として残る。

頂点 3 を質問して答え 2：頂点 4, 5 が可能性のある頂点として残る。

頂点 4 を質問して答え 2：頂点 5 のみが残る。

• これにより、3 回の質問で十分であることが示される。Alice はまず葉 2 を質問する。Bob が 0 または 1 と答えた場合、秘密の頂点は即座に決定される。最悪の答えは 2 で、葉 3, 4, 5 が残る。次に Alice は葉 3 を質問し、最悪の場合、葉 4, 5 が残る。最後の 1 回の質問でそれらを区別できる。
• 2 回の質問では不十分である。最初の質問の後、Bob は少なくとも 3 つの葉を可能性として残すことができる。スターの 3 つの葉に対して、もう一度距離の質問をしても全てを区別することはできない。なぜなら、少なくとも 2 つの葉は質問された頂点からの距離が同じになるからである。