#include <iostream>

#include <cstdio>

#include <queue>

#include <algorithm>

#include <cmath>

#include <cstring>

#define inf 2147483647

#define N 10100

#define p(a) putchar(a)

#define For(i,a,b) for(register long long i=a;i<=b;++i)

//by war

//2019.8.22

using namespace std;

long long T,n,x,y,cnt,tot;

long long prime[N],mu[N],ans[];

bool vis[N];

struct dian{

    long long l,r,t;

}a[N];

struct node{

    long long n;

    node *next;

}*e[N];

inline void in(long long &x){

    long long y=;char c=getchar();x=;

    while(c<''||c>''){if(c=='-')y=-;c=getchar();}

    while(c<=''&&c>=''){ x=(x<<)+(x<<)+c-'';c=getchar();}

    x*=y;

}

inline void o(long long x){

    if(x<){p('-');x=-x;}

    if(x>)o(x/);

    p(x%+'');

}

inline void push(long long x,long long y){

    node *p;

    p=new node();

    p->n=y;

    if(e[x]==)

        e[x]=p;

    else{

        p->next=e[x]->next;

        e[x]->next=p;

    }

}

void Euler(){

    mu[]=;

    For(i,,){

        if(!vis[i]) prime[++cnt]=i,mu[i]=-;

        for(register long long j=;j<=cnt&&i*prime[j]<=;j++){

            vis[i*prime[j]]=;

            if(i%prime[j]==){

                mu[i*prime[j]]=;

                break;

            }

            mu[i*prime[j]]=-mu[i];

        }

    }

}

long long dfs(long long x,long long fa,long long w){

    long long res=;

    for(node *i=e[x];i;i=i->next)

        if(i->n!=fa)

            res+=dfs(i->n,x,w*a[i->n].t);

    return res+w;

}

inline long long F(register long long d){

    long long res=,kk=;

    For(i,,n){

        a[i].t=a[i].r/d-a[i].l/d;

        if(a[i].l%d==)

            a[i].t++;

    }

    For(i,,n){

        res+=dfs(i,i,a[i].t);

        res-=a[i].t;

        kk+=a[i].t;

    }

    return res/+kk;

}

inline void clear(){

    For(i,,)

        e[i]=;

    memset(ans,,sizeof(ans));

}

signed main(){

    in(T);

    Euler();

    while(T--){

        clear();

        in(n);

        For(i,,n-){

            in(x);in(y);

            push(x,y);

            push(y,x);

        }

        For(i,,n) in(a[i].l);

        For(i,,n) in(a[i].r);

        For(i,,)

            for(register long long d=i;d<=;d+=i)

                ans[i]+=mu[d/i]*F(d);

        printf("Case %lld:\n",++tot);

        For(i,,){

            o(i);p(':');p(' ');

            o(ans[i]);p('\n');

        }

    }

    return ;

}