#include<bits/stdc++.h>
using namespace std;
const int N=63;
typedef unsigned int uint;
int C,T,m,n;
uint f[2][N][N][2][2],ans;
char s[N*3],s1[N],s2[N];
void DP(int A,int B,int C){
	if(C<0)return;
	memset(f,0,sizeof(f));
	f[0][0][0][!A][!B]=1;
	for(int i=0,p=0,q=1;i<m;++i,p^=1,q^=1){
		for(int a=0;a<=n;++a)
			for(int b=0;b<=n;++b){
				int c=i-a-b,w;
				if(c<0||c>n)continue;
				for(int u=0;u<2;++u)for(int v=0;v<2;++v)if(w=f[p][a][b][u][v]){
					f[p][a][b][u][v]=0;
					if((s[i]=='A'||s[i]=='?')&&a+1-c<=A)f[q][a+1][b][u|(a+1-c==A)][v]+=w;
					if((s[i]=='B'||s[i]=='?')&&b+1-a<=B)f[q][a][b+1][u][v|(b+1-a==B)]+=w;
					if((s[i]=='C'||s[i]=='?')&&c+1-b<=C)f[q][a][b][u][v]+=w;
				}
			}
	}
	ans+=f[m&1][n][n][1][1];
}
void solve(){
	scanf("%d",&n);
	scanf("%s%s%s",s1,s2,s);
	if(T)return puts("-1"),void();
	m=3*n,ans=0;
	for(int A=0;A<=n;++A)for(int B=0;B+A<=n;++B){
		int a=A,b=B;
		while(a<=n&&s1[a]=='0')++a;
		while(b<=n&&s2[b]=='0')++b;
		DP(A,B,n-a-b);
	}
	printf("%u\n",ans);
}
int main(){
	scanf("%d%d",&T,&C);
	while(T--)solve();
	return 0;
}