题目描述

有一棵以节点1为根节点的树，树的每个叶子节点上都有一个虫子，每个虫子都会先后朝着根节点爬行，每当一个虫子到一个无所有者的节点，就会将这个节点收入麾下，并获得1块钱。

当一个虫子爬到了根节点，或者爬到有所有者的节点，就停止爬行。

前一个虫子爬完了，后一个虫子才能开始爬。

你可以决定虫子的爬行顺序，请问虫子的总财产有多少块钱。

格式

• 多组输入

输入格式

第一行输入一个正整数$t$，表示一共有$t$个测试样例$(1 \le t \le 10^5)$

对于每个测试样例

• 第一行是一个整数$n(1 \le n \le 2*10^5)$，表示树一共有$n$个节点

• 接下来$n-1$行，每行有两个整数$u,v(1 \le u \le n,1 \le v \le n)$，代表节点u和节点v之间有一条边

输出格式

对于每个测试样例，输出一个正整数，虫子的总财产是多少块钱。

样例

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

5
3