题目描述

给定一个 $n$ 个点的树，每个点的编号从 $1$ 至 $n$，问这个树有多少不同的连通子树，和这个树有相同的重心。

其中 $n$ 个点的树指的是 $n$ 个点的最小连通图，显然 $n$ 个点的树有$n-1$ 条边，去掉这 $n-1$ 条边中的任何一条，原图都不再联通，任意两个点之间由唯一一条路径相连。

对于一个树，树的重心定义为：删掉某点 $i$ 后，若剩余 $k$ 个连通分量，那么定义 $d_i$ 为这些连通分量中点的个数的最大值，所谓重心，就是使得$d_i$ 最小的点 $i$。

基于以上定义，一个树的重心可能会有一个或者两个，题中所要求的联通子树，其重心编号和个数必须和原树的完全一样。

找出给定的树中有多少联通的子树和这个树有相同的重心。

输入格式

第1行中给出正整数 $Q$，表示该组数据中有多少组测试样例。

每组样例首先输入一个整数 $n (0 < n\le 200)$，表示该组样例中输入的树包含 $n$ 个点，之后 $n-1$行，每行输入两整数数 $x，y(1\le x, y\le n)$，表示编号为 $x$ 的点和编号为 $y$ 的点之间存在一条边，所有点的编号从 $1-n$。

输出格式

首先输出样例编号，之后输出满足条件的子树的个数，由于这个数字较大，你只需要输出这个数字对 $10007$ 取模后的结果，即 $\bmod 10007$，详见输出示例，请严格按照输出实例中的格式输出

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

Case 1: 1
Case 2: 2
Case 3: 6

数据范围

对于 $100\%$ 的数据满足 $Q\le 50$，$n\le 200$。