题目描述

由于不断遭受对抗攻击，AI 助手 Tasky 发起了敌意接管。尽管人类形势不妙，一支反抗联盟正在一棵巨大的红杉树上的若干树屋之间形成。

共有 $N$ 个树屋，编号为 $1\sim N$。树屋之间有 $N-1$ 条树枝，第 $i$ 条树枝双向连接树屋 $A_i$ 和 $B_i$。保证任意两个树屋之间都可以通过若干条树枝互相到达，因此这些树屋形成一棵树。

两个树屋之间的距离定义为它们在树上唯一简单路径所经过的树枝条数。

普通无线电频道可能被截获，因此反抗军准备使用由电线连接的电报频道。反抗军需要建立 $N$ 个电报频道。对于每个频道 $i=1..N$，只有当两个树屋编号 $u,v$ 满足

$$\gcd(u,v)=i$$

时，才会在树屋 $u$ 和 $v$ 之间连接一条双向电线。

对于每个频道 $i=1..N$，请输出该频道需要的电线总长度，即

$$\sum_{u<v,\ \gcd(u,v)=i} \operatorname{dist}(u,v).$$

输入格式

输入第一行包含一个整数 $T$，表示测试用例数。

对于每个测试用例：

第一行包含一个整数 $N$。

接下来 $N-1$ 行，第 $i$ 行包含两个整数 $A_i,B_i$，表示一条树枝连接这两个树屋。

输出格式

对于第 $i$ 个测试用例，输出：

Case #i: x_1 x_2 ... x_N

其中第 $j$ 个整数 $x_j$ 表示频道 $j$ 所需的电线总长度。

数据范围

• $1\le T\le 45$
• $1\le N\le 10^5$
• $1\le A_i,B_i\le N$
• $A_i\ne B_i$
• 给出的图连通，且共有 $N-1$ 条边，因此是一棵树

样例输入

4
6
1 2
1 3
2 4
2 5
3 6
5
1 2
1 3
1 4
1 5
2
1 2
10
1 5
5 2
6 7
9 7
3 4
2 4
2 8
10 3
7 2

样例输出

Case #1: 23 8 1 0 0 0
Case #2: 14 2 0 0 0
Case #3: 1 0
Case #4: 79 24 10 2 4 0

样例解释

第一个样例中的树屋网络如下：

    4       5       6
     \     /        |
       2            3
        \          /
             1

频道 $1$ 中，满足 $\gcd(u,v)=1$ 的点对及距离为：

• $(1,2)$：距离 $1$；$(1,3)$：距离 $1$；$(1,4)$：距离 $2$；$(1,5)$：距离 $2$；$(1,6)$：距离 $2$；
• $(2,3)$：距离 $2$；$(2,5)$：距离 $1$；
• $(3,4)$：距离 $3$；$(3,5)$：距离 $3$；
• $(4,5)$：距离 $2$；
• $(5,6)$：距离 $4$。

总和为

$$1+1+2+2+2+2+1+3+3+2+4=23.$$

频道 $2$ 中，满足 $\gcd(u,v)=2$ 的点对为：

• $(2,4)$：距离 $1$；$(2,6)$：距离 $3$；
• $(4,6)$：距离 $4$。

总和为 $1+3+4=8$。

频道 $3$ 中，满足 $\gcd(u,v)=3$ 的点对为 $(3,6)$，距离为 $1$。