题目描述

一片山地保护区的道路网络是一棵包含 $n$ 个节点的树，节点编号为 $1\sim n$。

一辆越野车最初停在节点 $1$。林澈与陆遥准备在这张道路网络上进行一场“越走越远”的挑战。

第一回合由林澈驾驶，之后两人轮流驾驶。每一回合，当前驾驶者必须沿树上的一条简单路径行驶，车辆在本回合结束时所在的节点，将成为下一回合的起点。

从第二回合开始，本回合经过的边数必须严格大于上一回合经过的边数。若轮到某位选手时，不存在满足要求的行驶路线，则该选手失败。两人都会采取最优策略。

为了研究不同开放区域对比赛结果的影响，他们会枚举道路树中所有包含节点 $1$ 的连通块，并在每个这样的连通块中独立进行一局上述游戏。

请你计算其中陆遥获胜的游戏局数，并对 $10^9+7$ 取模。

输入格式

第一行包含一个整数 $T$，表示数据组数。

对于每组数据：

第一行包含一个整数 $n$，表示树中的节点数。

接下来 $n-1$ 行，每行包含两个整数 $u_i,v_i$，表示树中的一条无向边。

输出格式

对于每组数据，输出一行：

Case #x: y

其中 $x$ 表示数据组编号，$y$ 表示陆遥获胜的游戏局数对 $10^9+7$ 取模后的结果。

样例

样例 1

样例输入

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

样例输出

Case #1: 1
Case #2: 5

数据范围与提示

本题采用子任务捆绑测试。

子任务 $1$（$8$ 分）：$n\leq 20$；
子任务 $2$（$20$ 分）：$n\leq 100$；
子任务 $3$（$16$ 分）：除节点 $1$ 外，其余节点的度数均不超过 $2$；
子任务 $4$（$16$ 分）：对于所有 $i\in[1,n-1]$，均有 $u_i=i+1$，且 $v_i$ 在 $[1,i]$ 中均匀随机生成；
子任务 $5$（$24$ 分）：$n\leq 30\,000$；
子任务 $6$（$16$ 分）：无特殊限制。

所有数据满足：

$$1\leq T\leq 10,\qquad 1\leq n\leq 2\times 10^5,\qquad 1\leq u_i,v_i\leq n.$$