## 【HDU 1693】Eat the Trees

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = 5000;

LL f[12][12][MAXN];
int MX,n,m,mat[12][12];

int main(){
int TT; cin>>TT;
for (int T=1;T<=TT;T++) {
scanf("%d%d",&m,&n); MX =1<<n+1;
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++)
scanf("%d",&mat[i][j]),memset(f[i][j],0,sizeof(f[i][j]));

if (mat[1][1]) f[1][1][3] = 1;
else f[1][1][0] = 1;
for (int j=1;j<=m;j++) {
for (int i=1;i<n;i++) {
for (int k=0;k<MX;k++) if (f[i][j][k]) {
bool up=k&(1<<i+1), left=k&(1<<i);
if (mat[i+1][j]) {
if (up && left) f[i+1][j][k^(1<<i)^(1<<i+1)] += f[i][j][k];
else if (up || left) {
f[i+1][j][k] += f[i][j][k];
f[i+1][j][k^(1<<i+1)^(1<<i)] += f[i][j][k];
} else {
f[i+1][j][k^(1<<i+1)^(1<<i)] += f[i][j][k];
}
} else {
if (!up && !left) f[i+1][j][k] += f[i][j][k];
}
}
}
for (int k=0;k<MX;k++) if (f[n][j][k] && (k&(1<<n)) == 0) {
int up = k & 1;
if (mat[1][j+1]) {
if (up) {
f[1][j+1][((k^1)<<1)^1] += f[n][j][k];
f[1][j+1][((k^1)<<1)^2] += f[n][j][k];
} else {
f[1][j+1][(k<<1)^3] += f[n][j][k];
}
} else {
if (!up) f[1][j+1][k<<1] += f[n][j][k];
else continue;
}
}
}
printf("Case %d: There are %I64d ways to eat the trees.\n",T,f[n][m][0]);
}
return 0;
}