距离圣诞节还有一个多月，但熊猫先生已经开始准备圣诞节了。熊猫先生正在用一套俄罗斯套娃装饰一棵圣诞树。共有 $n$ 个俄罗斯套娃，编号为 $1, 2, \dots, n$。第 $i$ 个套娃被设计为可以完美地嵌套在第 $(i+1)$ 个套娃中（对于所有 $1 \le i \le n-1$）。只有当套娃的编号相邻时，嵌套才是稳定的，否则较小的套娃会从较大的套娃中滑出。套娃可以递归嵌套。例如，$n$ 个套娃可以从最小到最大一直嵌套，直到只剩下一个套娃。

这棵圣诞树恰好有 $n$ 个节点，每个节点上悬挂着一个俄罗斯套娃，其中编号为 $1$ 的套娃被放置在树根处。熊猫先生邀请他的朋友绵羊先生在平安夜从圣诞树上收集一些套娃作为礼物。绵羊先生会选择一个树节点，并收集以该节点为根的子树中的所有套娃。

由于套娃数量可能很多，绵羊先生想把他收集到的套娃嵌套起来以便携带。他想知道对于每一个树节点，如果他尽可能多地嵌套这些套娃，最终会剩下多少个套娃。注意，套娃必须稳定地嵌套。

输入格式

第一行输入包含测试用例的数量 $T$ ($1 \le T \le 10$)。接下来是 $T$ 个测试用例。 每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$)，表示套娃的数量，也是树节点的数量。 接下来的 $(n-1)$ 行，每行包含两个整数 $x$ 和 $y$ ($1 \le x, y \le n$)，表示编号为 $x$ 和 $y$ 的套娃在圣诞树上是相邻的。 保证所有测试用例中 $n$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，输出一行，以 “Case #x:” 开头（$x$ 为测试用例编号，从 $1$ 开始），后跟 $n$ 个整数。第 $i$ 个 ($1 \le i \le n$) 整数表示如果绵羊先生选择包含编号为 $i$ 的套娃的树节点，收集该子树中的所有套娃，并尽可能多地进行稳定嵌套，最终剩下的套娃数量。

样例

输入 1

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

输出 1

Case #1: 1 3 3 1 1 1 1