#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105,mod=1e9+7;
int n,m,Case;
ll f[3][N];
void solve() {
	scanf("%d%d",&n,&m),f[0][1]=f[1][2]=1,f[2][2]=(m%6==0);
	for(int i=2;i<=n;i++) {
		f[0][i]=(f[1][i-1]+f[2][i-1])%mod;
		if(i>2)f[1][i]=(f[0][i-2]+f[2][i-2])%mod;
		if(i>2&&m%6==0)f[2][i]=(f[0][i-2]+f[1][i-2])%mod;
	}
	printf("Case #%d: %lld\n",++Case,(f[0][n]+f[1][n]+f[2][n])%mod);
}
int main() {
	int tt;scanf("%d",&tt);
	while(tt--)solve();
	return 0;
}