树是一个没有环的连通图。
有根树是指其中一个特殊顶点被称为根的树。如果在一棵有根树中，顶点 X 和 Y 之间有一条边，且 X 比 Y 更靠近根（换句话说，从根到 X 的最短路径比从根到 Y 的最短路径短），则称 Y 是 X 的子节点。
满二叉树是一种有根树，其中每个节点要么恰好有两个子节点，要么没有子节点。
给定一棵包含 N 个节点（编号从 1 到 N）的树 G。你可以删除一些节点。当删除一个节点时，与该节点相连的边也会被删除。你的任务是删除尽可能少的节点，使得剩余的节点在选择某个节点作为根后，能够构成一棵满二叉树。
输入格式
输入的第一行包含测试用例的数量 T。接下来是 T 个测试用例。每个测试用例的第一行包含一个整数 N，表示树中的节点数。接下来的 N-1 行，每行包含两个用空格分隔的整数 Xi 和 Yi，表示 G 中存在一条连接 Xi 和 Yi 的无向边。
输出格式
对于每个测试用例，输出一行 "Case #x: y"，其中 x 是测试用例编号（从 1 开始），y 是为了使剩余节点构成满二叉树所需删除的最少节点数。
数据范围
$1 \le T \le 100$ $1 \le X_i, Y_i \le N$ 每个测试用例都将构成一棵有效的连通树。
小数据集（9 分）
$2 \le N \le 15$
大数据集（21 分）
$2 \le N \le 1000$
样例
样例输入 1
3 3 2 1 1 3 7 4 5 4 2 1 2 3 1 6 4 3 7 4 1 2 2 3 3 4
样例输出 1
Case #1: 0 Case #2: 2 Case #3: 1
说明
在第一个用例中，G 本身就是一棵满二叉树（如果我们以节点 1 为根），因此不需要进行任何操作。
在第二个用例中，我们可以删除节点 3 和 7；此时 2 可以作为满二叉树的根。
在第三个用例中，我们可以删除节点 1；此时 3 将成为满二叉树的根（我们也可以删除节点 4；此时可以将 2 作为根）。