题目背景

“说实话，最喜欢你了；因为长得好看，所以最喜欢你了。

你的性格，我最喜欢了；虽然不太清楚，但是最喜欢了。”

赫尔德最近加入了一个奇怪的社区，那里面流行一种“配对追星”的活动。大家在人群中找到那个最耀眼的人，就作为自己的偶像了。

题目描述

赫尔德不知道这样是否好，为了研究这个活动，她想先从这个活动能持续多久开始研究。于是她抽象了这个问题。

给定一棵树，共 $n$ 个点，分别编号为 $1\sim n$。

每次操作，你需要选出三个点 $a,b,c$ 将他们标记，满足：

• $c$ 是 $a$ 到 $b$ 简单路径上编号最大的点；
• $a,b,c$ 两两不同；
• $a,b,c$ 先前都没有被标记过。

问至多能进行多少次操作。

---

【提示】

树上 $p$ 到 $q$ 的简单路径是指一个数列 $a_1,\dots,a_k$，满足：

1. $a_1=p$，$a_k=q$；
2. 其中没有重复元素；
3. 对于所有 $1\le i<k$，$a_{i+1}$ 与 $a_i$ 有边相连。

输入格式

本题有多组数据。

第一行是数据组数 $T$，接下来 $T$ 组数据，每组数据格式如下：

第一行一个正整数 $n$。

接下来 $n-1$ 行，每行两个正整数 $x,y$，描述树上的一条连接 $x,y$ 的边。

输出格式

对于每组数据输出一行一个非负整数，为答案。

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

1
1
2

提示

【样例解释】

对于第一组数据，可以选择 $a=1,b=2,c=3$。

对于第三组数据，可以依次选择 $a=3,b=4,c=7$，$a=1,b=2,c=5$。

---

【数据范围】

设 $S$ 为每个测试点所有数据中 $n$ 的和。

对于所有数据：$1\le T\le 3\times 10^4$，$1\le n\le 2\times 10^5$，$S\le 6\times 10^5$。

$$\begin{array}{c|c|c|c|c|c} \hline \textbf{子任务编号} & ~~~~~~~n\le ~~~~~~~ & ~~~~~~~S\le ~~~~~~~ & \textbf{特殊性质} & \textbf{子任务依赖} & \textbf{~~~分数~~~} \\ \hline \textsf{1} & 5 & & & & 3 \\ \hline \textsf{2} & 20 & 60 & & & 5 \\ \hline \textsf{3} & & & \textsf{B} & & 12 \\ \hline \textsf{4} & 333 & 10^3 & \textsf{A} & & 9 \\ \hline \textsf{5} & 333 & 10^3 & & \textsf{2,4} & 7 \\ \hline \textsf{6} & 3333 & 10^4 & \textsf{A} & \textsf{4} & 15 \\ \hline \textsf{7} & 3333 & 10^4 & & \textsf{5,6} & 13 \\ \hline \textsf{8} & & & \textsf{A} & \textsf{6} & 12 \\ \hline \textsf{9} & & & & \textsf{1,3,7,8} & 24 \\ \hline \end{array} $$

特殊限制 $\textsf{A}$：保证树的形态是一条链，即树上不存在度数大于 2 的点。

特殊限制 $\textsf{B}$：保证树随机生成：对于每个整数 $i\in [2,n]$，均匀随机选择整数 $j\in [1,i-1]$ 并在 $i,j$ 间连边，然后随机打乱点的编号。