#include <bits/stdc++.h>
using namespace std;
#define TR(i,v)       for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i)
#define DEBUG(x)      cout<<#x<<" = "<<x<<endl
#define SIZE(p)       (int)(p).size()
#define MP(a,b)       make_pair((a),(b))
#define ALL(p)        (p).begin(),(p).end()
#define rep(i,n)      for(int i=0;i<(int)(n);++i)
#define REP(i,a,n)    for(int i=(a);i<(int)(n); ++i)
#define FOR(i,a,b)    for(int i=(int)(a);i<=(int)(b);++i)
#define FORD(i,b,a)   for(int i=(int)(b);i>=(int)(a);--i)
#define CLR(x,y)      memset((x),(y),sizeof((x)))
typedef long long LL;
typedef pair<int,int> pii;
const int N=10005,mod=21092013;
int n,L[N],H[N],dp[N][2],C[N];
vector<int> g[N];
int add(int x,int y){
  x+=y;if(x>=mod)x-=mod;
  return x;
}
int mul(int x,int y){
  return (LL)x*y%mod;
}
int sub(int x,int y){
  x-=y;if(x<0)x+=mod;
  return x;
}
void dfs(int u,int f){
  dp[u][0]=C[u],dp[u][1]=C[u];
  int ps=0;
  for(int v:g[u])if(v!=f){
    dfs(v,u);
    dp[u][0]=add(dp[u][0],dp[v][0]);
    dp[u][0]=add(dp[u][0],mul(dp[v][1],C[u]));
    dp[u][0]=add(dp[u][0],mul(dp[v][1],ps));
    ps=add(ps,mul(dp[v][1],C[u]));
    dp[u][1]=add(dp[u][1],mul(dp[v][1],C[u]));
  }
}
int main(){
  int T;scanf("%d",&T);
  FOR(cs,1,T){
    printf("Case %d:\n",cs);
    scanf("%d",&n);
    rep(i,n)g[i].clear();
    rep(i,n-1){
      int u,v;scanf("%d%d",&u,&v);--u,--v;
      g[u].push_back(v),g[v].push_back(u);
    }
    rep(i,n)scanf("%d",L+i);
    rep(i,n)scanf("%d",H+i);
    int f[51];
    FORD(g,50,1){
      rep(i,n)C[i]=H[i]/g-(L[i]-1)/g;
      dfs(0,-1);
      f[g]=dp[0][0];
      for(int j=g+g;j<=50;j+=g)f[g]=sub(f[g],f[j]);
    }
    FOR(i,1,50)printf("%d: %d\n",i,f[i]);
  }
  return 0;
}