#include<bits/stdc++.h>
#define ui unsigned int
using namespace std;
typedef array<ui,4> arr;
const int N=65;
char s[N*3],s1[N],s2[N];
int n;
arr dp[N][N][N];
void solve() {
	scanf("%d%s%s%s",&n,s1,s2,s);
	if(n!=60) return puts("-1"),void();
	s1[n+1]=s2[n+1]='1';
	ui ans=0;
	for(int A=0;A<=n;++A) for(int B=0;B<=n;++B) {
		int ca=A,cb=B;
		while(s1[ca]=='0') ++ca;
		while(s2[cb]=='0') ++cb;
		int C=n-A-B;
		if(C<0) continue;
		memset(dp,0,sizeof(dp)),dp[0][0][0][(A?0:2)|(B?0:1)]=1;
		for(int a=0;a<=n;++a) for(int b=0;b<=n&&b-a<=B;++b) for(int c=max(a-A,0);c<=n&&c<=b+C;++c) {
			arr &f=dp[a][b][c];
			const char z=s[a+b+c];
			if((z=='?'||z=='A')&&a<n&&a-c<A) {
				arr &ga=dp[a+1][b][c];
				if(a-c==A-1) ga[2]+=f[0]+f[2],ga[3]+=f[1]+f[3];
				else ga[0]+=f[0],ga[1]+=f[1],ga[2]+=f[2],ga[3]+=f[3];
			}
			if((z=='?'||z=='B')&&b<n&&b-a<B) {
				arr &gb=dp[a][b+1][c];
				if(b-a==B-1) gb[1]+=f[0]+f[1],gb[3]+=f[2]+f[3];
				else gb[0]+=f[0],gb[1]+=f[1],gb[2]+=f[2],gb[3]+=f[3];
			}
			if((z=='?'||z=='C')&&c<n&&c-b<C) {
				arr &gc=dp[a][b][c+1];
				gc[0]+=f[0],gc[1]+=f[1],gc[2]+=f[2],gc[3]+=f[3];
			}
		}
		ans+=dp[n][n][n][3];
	}
	printf("%u\n",ans);
}
signed main() {
	int T,id; scanf("%d%d",&T,&id);
	while(T--) solve();
	return 0;
}