小红的奇数奶油球

题号：NC312057
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小红制作了一个精美的创意甜品，该甜品由 $n$ 个奶油球（编号 $1$ 到 $n$ ）组成。这些奶油球之间通过奶油拉花连接，恰好构成一棵树的结构。
$\hspace{15pt}$ 小红认为，一个奶油球是“完美的”，当且仅当满足以下条件：
$\hspace{23pt}\bullet\,$ 如果将这个奶油球以及与之相连的所有拉花拆除，剩下的每一个连通部分（即剩下的奶油球簇，或者严谨的说，极大连通分量）所包含的奶油球个数都必须是奇数。
$\hspace{23pt}\bullet\,$ 特别的，如果整棵树只有 $1$ 个节点，那么认为该节点是“完美的”。
$\hspace{15pt}$ 小红想知道，在这个甜品中共有多少个“完美的”奶油球？

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个整数 ，表示奶油球的数量。
此后  行，第  行输入两个整数  和 ，表示奶油球  和  之间有一条奶油拉花相连。保证所有的拉花连接构成一棵树

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每组测试数据，新起一行输出一个整数，表示“完美的”奶油球的总数。

示例1

输入

复制

输出

复制

1
1
4

说明

对于第一组测试数据：
移除 ：剩  大小 ，不满足；
移除 ：剩 、 大小 、，满足；
移除 ：剩  大小 ，不满足；
因此，只有编号为  的奶油球是符合条件的“完美的”奶油球，答案为 。

对于第二组测试数据：
移除 ：剩 、 大小 、，满足；
移除 ：剩  大小 ，不满足；
移除 ：剩 、、 大小 、、，不满足；
移除 ：剩  大小 ，不满足；
移除 ：剩  大小 ，不满足；
因此，只有编号为  的奶油球是符合条件的“完美的”奶油球，答案为 。