#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int MAXN = 1E5 + 10;

int val[MAXN], ans[MAXN];
vector<int> div[MAXN];
vector<int> E[MAXN];

int cnt[MAXN];

int count(vector<int> a, bool add = false){
	static int num[1 << 6] = {1};
	int limit = 1 << a.size(), ret = 0;
	ret = cnt[1];
	for (int t, i = 1; i < limit; ++i){
		t = 31 - __builtin_clz(i);
		num[i] = num[i ^ 1 << t] * a[t];
		ret += __builtin_popcount(i) & 1 ? -cnt[num[i]] : cnt[num[i]];
		cnt[num[i]] += add;
	}
	cnt[1] += add;
	return ret;
}

void DFS(int u, int pre){
	int temp = count(div[val[u]], true);
	for (int i = 0; i < E[u].size(); ++i)
		if (E[u][i] != pre)
			DFS(E[u][i], u);
	ans[u] = count(div[val[u]]) - temp;
}

int main(){
	for (int i = 1; i < MAXN; ++i){
		div[i].reserve(6);
		int j = 2, t = i;
		for (; j * j <= t; ++j)
			if (t % j == 0){
				div[i].push_back(j);
				for (; t % j == 0; t /= j);
			}
		if (t > 1)
			div[i].push_back(t);
	}

	int n;
	for (int casi = 1; scanf("%d", &n) == 1; ++casi){
		for (int i = 1; i <= n; ++i)
			E[i].clear();
		for (int u, v, i = 1; i < n; ++i){
			scanf("%d%d", &u, &v);
			E[u].push_back(v);
			E[v].push_back(u);
		}
		for (int i = 1; i <= n; ++i)
			scanf("%d", &val[i]);
		memset(cnt, 0, sizeof(cnt));
		DFS(1, 0);
		printf("Case #%d:", casi);
		for (int i = 1; i <= n; ++i)
			printf(" %d", ans[i]);
		puts("");
	}
	return 0;
}