题目描述

牛牛有一棵 $n$ 个点的有根树，根为 $1$。

我们称一个长度为 $m$ 的序列 $a$ 是好的，当且仅当：

• $\forall i\in(1,m]$，$a_i$ 为 $a_{i-1}$ 的祖先或 $a_{i-1}$ 是 $a_i$ 的祖先；
• $\forall 1\le i<j\le m$，$a_i\not=a_j$。

你需要帮助牛牛求出最长的好的序列长度。

输入格式

第一行一个正整数 $T$，表示数据组数。

对于每组数据第一行一个正整数 $n$。

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

输出格式

$T$ 行，每行一个整数表示每组数据的答案。

样例

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

7

另有 $4$ 组大样例在题目附件中，其中样例 $3,4,5$ 分别满足下面的特殊性质 $\text{A,B,C}$。

数据范围

对于 $100\%$ 的数据，$1\le T\le 5$，$2\le n\le 10^5$，$1\le u,v\le n$，$u\not=v$，输入保证是一棵树。

特殊性质 $\text{A}$：给出的树为链，其中 $1$ 号点的度数为 $1$。

特殊性质 $\text{B}$：给出的树为菊花，其中 $1$ 号点的度数为 $n-1$。

特殊性质 $\text{C}$：给出的树为完全二叉树。