题目描述

给定一棵无根树，请计算满足以下条件的节点数量：如果以该节点为根，那么以这个节点为根的树是一棵二叉树。

注意：一棵二叉树是一棵根树，其中每个节点最多有两个子节点。

输入格式

第一行一个整数 $T (1 \leq T \leq 100)$，表示数据组数，对于每组数据：
输入的第一行包含一个整数 $n(1 \le n \le 10^{5})$表示节点的数量。
接下来的 $n−1$ 行，每行包含两个整数 $u(1 \le u \le n)$ 和 $v(1 \le v \le n)$，表示存在一条连接节点 $u$ 和 $v$ 的边，保证这 $n−1$ 条边构成一棵树。

输出格式

输出$T$行，每行一个整数，表示满足条件的节点数量。

样例

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

5
3

除了$2$号节点其他节点都满足条件
第一组的树如下：