在与对手进行了一场激烈的战斗后，布鲁斯·韦恩（Bruce Wayne）最终赢得了选举，成为了哥谭市的市长。像其他政治家一样，他为了哥谭市的繁荣制定了许多项目计划，但他遇到了同样的问题：资金短缺。

他决定换个角度处理这个问题；他将允许公司购买城市中的道路（城市中的道路是无向的）。城市将获得项目所需的资金，而公司则可以利用这些道路进行广告宣传（他是这么想的）。

交易完成后，这些公司比他预想的要狡猾得多。他们开始威胁说，他们将封锁城市中的某一条道路，阻止人们去上班，并希望人们会起来反抗韦恩市长。该问题指出，城市被设计成了一棵连通的树，即任意两个区域之间只有一条唯一的路径。因此，封锁一条道路意味着某些区域将无法再从其他区域到达。

韦恩市长与他的委员会讨论了这个问题，并确定了他们所谓的“脆弱道路”。如果封锁一条道路会导致两个区域之间不再连通，那么这条道路就是脆弱的。韦恩市长希望通过修建更多的道路来防止这种情况发生，但他的预算只能负担修建一条额外的道路。你能帮他找出应该修建哪条道路，使得脆弱道路的数量最少吗？

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量（$1 \le T \le 100$）。每个测试用例的第一行包含一个整数 $N$，表示城市中的区域数量（$1 \le N \le 10,000$）。接下来的 $N - 1$ 行，每行包含一对由空格分隔的整数 $x$ 和 $y$（$1 \le x, y \le N$），表示区域 $x$ 和区域 $y$ 之间有一条道路。保证这些边构成一棵树。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示修建新道路后城市中剩余的最少脆弱道路数量。

样例

输入 1

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

输出 1

0
1