#include<bits/stdc++.h>
using namespace std;
const int N=63;
typedef unsigned int uint;
int C,T,m,n;
uint f[N][N][N][4],ans;
char s[N*3],s1[N],s2[N];
inline void DP(int A,int B,int C){
	if(C<0)return;
	f[0][0][0][0]=1;
	for(int a=0;a<=n;++a)for(int b=0;b<=n&&b<=a+B;++b)for(int c=max(0,a-A);c<=n&&c<=b+C;++c){
		int t=a+b+c;
		if(!t)continue;
		memset(f[a][b][c],0,sizeof(f[a][b][c]));
		if(a&&b-a<B&&(s[t]=='A'||s[t]=='?')){
			f[a][b][c][0]+=f[a-1][b][c][0];
			f[a][b][c][1]+=f[a-1][b][c][1];
			f[a][b][c][2]+=f[a-1][b][c][2];
			f[a][b][c][3]+=f[a-1][b][c][3];
		}
		if(b&&c-b<C&&(s[t]=='B'||s[t]=='?')){
			f[a][b][c][0]+=f[a][b-1][c][0];
			f[a][b][c][1]+=f[a][b-1][c][1];
			f[a][b][c][2]+=f[a][b-1][c][2];
			f[a][b][c][3]+=f[a][b-1][c][3];
		}
		if(c&&a-c<A&&(s[t]=='C'||s[t]=='?')){
			f[a][b][c][0]+=f[a][b][c-1][0];
			f[a][b][c][1]+=f[a][b][c-1][1];
			f[a][b][c][2]+=f[a][b][c-1][2];
			f[a][b][c][3]+=f[a][b][c-1][3];
		}
		if(b-a==B){
			f[a][b][c][1]+=f[a][b][c][0];
			f[a][b][c][3]+=f[a][b][c][2];
			f[a][b][c][0]=f[a][b][c][2]=0;
		}
		if(a-c==A){
			f[a][b][c][2]+=f[a][b][c][0];
			f[a][b][c][3]+=f[a][b][c][1];
			f[a][b][c][0]=f[a][b][c][1]=0;
		}
	}
	ans+=f[n][n][n][3];
}
void solve(){
	scanf("%d",&n);
	scanf("%s%s%s",s1,s2,s+1);
	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;
}