#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL mod=1000000007ll;
const int N=811,M=8;
int n,m;
int edgen[N][M],edgem[N][M];
int v[1011],nv=0;
int e[8],cnt[8],ncnt[8],st[8],ed[8],dir[16];
map<int,int> has;
void output(int x)
{
	printf("%d %d ",x,v[x]);x=v[x];
	int e[8];
	for (int i=m;i>=1;i--) e[i]=x&7,x>>=3;
	for (int i=1;i<=m;i++) printf("%d ",e[i]);printf("\n");
}
bool check(int maxn)
{
	for (int i=1;i<=maxn;i++) st[i]=-1;
	for (int i=1;i<=m;i++)
	{
		if (st[e[i]]==-1) st[e[i]]=i;
		ed[e[i]]=i;
	}
	for (int i=1;i<=maxn;i++) cnt[i]=0;
	for (int i=1;i<=m;i++) cnt[e[i]]++;
	for (int i=1;i<=maxn;i++)
	{
		if (st[i]==-1) continue;
		for (int j=1;j<=maxn;j++) ncnt[j]=0;
		for (int j=st[i];j<=ed[i];j++) ncnt[e[j]]++;
		for (int j=1;j<=maxn;j++)
			if (ncnt[j]!=0 && ncnt[j]!=cnt[j]) return false;
	}
	return true;
}
void dfs(int pos,int maxn)
{
	if (pos==m+1)
	{
		int ans=0;
		for (int i=1;i<=m;i++)
			ans<<=3,ans|=e[i];
		++nv;v[nv]=ans;has[ans]=nv;
		return;
	}
	if (pos==m+1) return;
	for (e[pos]=1;e[pos]<=maxn && e[pos]<=m;e[pos]++)
		dfs(pos+1,maxn+(e[pos]==maxn));
}
int chgto(int* e,int maxn)
{
	//cout<<"CHGTO\n";
	//for (int i=1;i<=m;i++) cout<<e[i]<<" ";cout<<endl;
	for (int i=1;i<=maxn;i++) dir[i]=-1;
	maxn=0;
	for (int i=1;i<=m;i++)
		if (dir[e[i]]==-1) dir[e[i]]=++maxn;
	for (int i=1;i<=m;i++)
		e[i]=dir[e[i]];
	//for (int i=1;i<=m;i++) cout<<e[i]<<" ";cout<<endl;
	maxn=0;
	for (int i=1;i<=m;i++)
		maxn<<=3,maxn|=e[i];
	return maxn;
}
LL g[2][1011];//ans
int f[2][1011];//mst
void work(int tcase)
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) for (int j=1;j<m;j++) scanf("%d",&edgen[i][j+1]);
	for (int i=1;i<n;i++) for (int j=1;j<=m;j++) scanf("%d",&edgem[i+1][j]);
	nv=0;has.clear();
	dfs(1,1);
	int now,last,fin=0;
	int a[8],b[8],idx;
	bool ok;
	now=1,last=0;
	memset(f[now],-1,sizeof(f[last]));
	memset(g[now],0,sizeof(g[last]));
	for (int i=1;i<=m;i++)
		fin<<=3,fin|=1;
	fin=has[fin];
	g[now][fin]=1;f[now][fin]=0;
	
	
	
	for (int x=1;x<=n;x++)
	{
		//cout<<f[now][deb]<<endl;
		for (int y=1;y<=m;y++)
		{
			if (x==1 && y==1) continue;
			swap(last,now);
			memset(f[now],-1,sizeof(f[now]));
			memset(g[now],0,sizeof(g[now]));
			for (int p=1,tem,ma,mm;p<=nv;p++)
			{
				if (f[last][p]==-1) continue;
				tem=v[p];
				for (int i=m;i>=1;i--) a[i]=tem&7,tem>>=3;
				mm=0;
				for (int i=1;i<=m;i++) cnt[i]=0;
				for (int i=1;i<=m;i++) cnt[a[i]]++;
				for (int i=1;i<=m;i++) if (mm<a[i]) mm=a[i];
				if (y==1)
				{
					idx=p;
					if (f[now][idx]==-1 || f[now][idx]>f[last][p]+edgem[x][y])
					{
						f[now][idx]=f[last][p]+edgem[x][y];
						g[now][idx]=g[last][p]*2%mod;
					}
					else if (f[now][idx]==f[last][p]+edgem[x][y])
						g[now][idx]+=g[last][p]*2%mod,g[now][idx]%=mod;
					if (cnt[a[1]]>1)
					{
						ma=mm;
						for (int i=1;i<=m;i++) b[i]=a[i];
						b[1]=++ma;
						idx=chgto(b,ma);
						if (has[idx]>0)
						{
							idx=has[idx];
							if (f[now][idx]==-1 || f[now][idx]>f[last][p])
							{
								f[now][idx]=f[last][p];
								g[now][idx]=g[last][p];
							}
							else if (f[now][idx]==f[last][p])
								g[now][idx]+=g[last][p],g[now][idx]%=mod;
						}
					}
				}
				else
				{
					if (cnt[a[y]]>1)
					{
						for (int i=1;i<=m;i++) b[i]=a[i];
						ma=mm;b[y]=++ma;
						idx=chgto(b,ma);
						if (has[idx]>0)
						{
							idx=has[idx];
							if (f[now][idx]==-1 || f[now][idx]>f[last][p])
							{
								f[now][idx]=f[last][p];
								g[now][idx]=g[last][p];
							}
							else if (f[now][idx]==f[last][p])
								g[now][idx]+=g[last][p],g[now][idx]%=mod;
						}
					}
					if (x>1)
					{
						idx=p;
						if (f[now][idx]==-1 || f[now][idx]>f[last][p]+edgem[x][y])
						{
							f[now][idx]=f[last][p]+edgem[x][y];
							g[now][idx]=g[last][p]*2%mod;
						}
						else if (f[now][idx]==f[last][p]+edgem[x][y])
							g[now][idx]+=g[last][p]*2%mod,g[now][idx]%=mod;
					}
					if (cnt[a[y]]>1)
					{
						for (int i=1;i<=m;i++) b[i]=a[i];
						b[y]=b[y-1];
						idx=chgto(b,mm);
						if (has[idx]>0)
						{
							idx=has[idx];
							if (f[now][idx]==-1 || f[now][idx]>f[last][p]+edgen[x][y])
							{
								f[now][idx]=f[last][p]+edgen[x][y];
								g[now][idx]=g[last][p]*2%mod;
							}
							else if (f[now][idx]==f[last][p]+edgen[x][y])
								g[now][idx]+=g[last][p]*2,g[now][idx]%=mod;
						}
					}
					if (x>1 && a[y]!=a[y-1])
					{
						for (int i=1;i<=m;i++) b[i]=a[i];
						for (int i=1;i<=m;i++) if (i!=y && b[i]==b[y]) b[i]=b[y-1];
						b[y]=b[y-1];
						idx=chgto(b,mm);
						if (has[idx]>0)
						{
							idx=has[idx];
							if (f[now][idx]==-1 || f[now][idx]>f[last][p]+edgem[x][y]+edgen[x][y])
							{
								f[now][idx]=f[last][p]+edgem[x][y]+edgen[x][y];
								g[now][idx]=g[last][p]*3%mod;
							}
							else if (f[now][idx]==f[last][p]+edgem[x][y]+edgen[x][y])
								g[now][idx]+=g[last][p]*3%mod,g[now][idx]%=mod;
						}
					}
				}
			}
			
			/*printf("XXXXXXX %d %d YYYYYYYY\n",x,y);
			for (int i=1;i<=nv;i++)
			{
				if (f[now][i]>=0)
				{
					output(i);
					printf("%d %lld\n",f[now][i],g[now][i]);
				}
			}*/
			
		}
	}
	printf("Case #%d: %d %lld\n",tcase,f[now][fin],g[now][fin]);
}			
							
int main()
{
	int T;
	scanf("%d",&T);
	for (int t=1;t<=T;t++) work(t);
}