题目描述

$Moon$ 有一颗树共有 $n$ 个节点，$n - 1$ 条边，根节点为 $1$ 。

根节点的上方还有一个 $0$ 号节点，每一秒可以从根节点通过一个节点到 $0$ 号节点，所有节点同时往 $0$ 号节点走，不可以两个节点同时存在于原树的同一个节点处，所有不能走的节点都需要等待一秒。请问所有节点都到 $0$ 号节点的最短时间是多少？一个节点已经到 $0$ 号节点不算等待时间。

输入格式

一个正整数 $t$（$1 \leq t \leq 2 \times 10^5$ ）表示样例组数。

每组样例包含一个正整数 $n$（$1 \leq n \leq 2 \times 10^5$ ）。

接下来 $n - 1$ 行每行两个正整数 $u,v$（$1 \leq u,v \leq n$）表示 $u,v$ 有一条边连接。

对于所有测试数据保证 $\sum n \leq 2 \times 10^5$。

输出格式

每行一个正整数表示最短时间。

输入样例

1
4 
1 2
1 3
1 4

输出样例

7

样例解释

设等待时间为 $d(i)$ ，移动时间为$f$，初始都为 $0$ 。

首先选择 $1-2$ 向上移动 $f+1$，$1$ 节点抵达。

此时 $d(1)=0,d(2)=0,d(3)=1,d(4)=1$ 。

接着选择 $2-3$ 向上移动 $f+1$，$2$ 节点抵达。

此时 $d(1)=0,d(2)=0,d(3)=1,d(4)=2$ 。

接着选择 $3-4$ 向上移动 $f+1$，$3$ 节点抵达。

此时 $d(1)=0,d(2)=0,d(3)=1,d(4)=2$ 。

接着选择 $4$ 向上移动 $f+1$，$4$ 节点抵达。

此时 $d(1)=0,d(2)=0,d(3)=1,d(4)=2$ 。

总时间 $=f+\sum\limits_{i=1}^nd_i$ 。