Knight of Diamonds, wielding contractions to forge a tree of perfect face.

对于一棵有标号无根树，定义一次 收缩 操作 $u \leftarrow v$ 为：

• 如果 $u, v$ 在当前树上不相邻则无事发生。
• 否则如果 $u, v$ 相邻，对于 $v$ 的所有非 $u$ 的邻居，将其和 $u$ 之间连一条无向边，然后删除 $v$ 和所有与其相连的边。

定义一棵有标号无根树为 无根满二叉树，当且仅当其可以通过选择一个结点作为根成为 满二叉树。

现在给定一棵大小为 $n$ 的有标号无根树 $G$，你想知道：可以通过若干次 收缩 操作变为树 $G$ 的 无根满二叉树，无根满二叉树原本的结点个数至少为多少。

可以证明始终存在一棵大小有限的无根满二叉树满足题目限制。

由于答案可能很大，假设答案为 $s$，你只需要输出 $\log_2(s+1)$ 即可。可以证明 $\log_2(s+1)$ 在题目的限制下始终为正整数。

（一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的高度为 $k$，且结点总数是 $2^k - 1$，则它就是满二叉树。）

输入格式

第一行一个正整数 $T$，表示这个测试点内测试数据的组数。对于每组测试数据：

• 第一行输入一个正整数 $n$。

• 接下来 $n - 1$ 行，每行两个正整数 $u, v$ 表示 $G$ 上的一条边 $(u, v)$。

输出格式

对于每组测试数据，输出一行一个正整数表示答案。

样例一

input

1
5
1 5
2 5
3 5
4 5

output

3

explanation

可以通过大小为 $7$ 的无根满二叉树通过两次收缩得到。

样例二

input

2
3
1 2
1 3
7
1 2
2 3
1 4
1 5
5 6
3 7

output

2
4

样例三～七

见附件下载。

限制与约定

对于所有数据，保证 $1 \leq \sum n \leq 10^6$。

“树形态”中，“菊花”指存在一个向所有点有直接连边的点，“链”指所有点度数不超过 $2$。

时间限制：$2\texttt{s}$

空间限制：$512\texttt{MB}$