#include <bits/stdc++.h>
using namespace std;
#define N 65
#define u32 unsigned int
int n;
u32 f[N*3][N][N][2][2];
char t[N],s1[N],s2[N];
void solve(){
	scanf("%d%s%s%s",&n,s1,s2,t+1);
	if(n!=50){puts("-1");return;}
	u32 ret=0;
	for(int x=0;x<=n;++x)
		for(int y=0;x+y<=n;++y){
			int z=n+1;
			for(int i=x;i<=n;++i)
				for(int j=y;i+j<=n;++j)
					if(s1[i]=='1'&&s2[j]=='1')z=min(z,i+j);
			if(z>n)continue;z=n-z;
			for(int i=0;i<=n*3;++i)
				for(int j=0,l,r;j<=min(n,i);++j){
					l=max(0,(i-j-z+1)/2),r=min(min(n,i),min(x+i-2*j,min(y+j,i-j)));
					for(int k=l;k<=r;++k)f[i][j][k][0][0]=f[i][j][k][0][1]=f[i][j][k][1][0]=f[i][j][k][1][1]=0;
				}
			int o=(!x),o1=(!y);
			f[0][0][0][o][o1]=1;
			for(int i=0;i<n*3;++i)
				for(int j=0,l,r;j<=min(n,i);++j){
					l=max(max(0,i-j-n),(i-j-z+1)/2),r=min(min(n,i),min(x+i-2*j,min(y+j,i-j)));
					if(t[i+1]=='?'){
						for(int k=l,m=i-j-k,o1,o2;k<=r;++k,--m){
							for(int a=0;a<2;++a)
								for(int b=0;b<2;++b){
									f[i+1][j+1][k][a|(j+1-m==x)][b]+=f[i][j][k][a][b];
									f[i+1][j][k+1][a][b|(k-j+1==y)]+=f[i][j][k][a][b];
									f[i+1][j][k][a][b]+=f[i][j][k][a][b];
								}
						}
					}else if(t[i+1]=='A'){
						for(int k=l,m=i-j-k,o1,o2;k<=r;++k,--m){
							for(int a=0;a<2;++a)
								for(int b=0;b<2;++b){
									f[i+1][j+1][k][a|(j+1-m==x)][b]+=f[i][j][k][a][b];
								}
						}
					}else if(t[i+1]=='B'){
						for(int k=l,m=i-j-k,o1,o2;k<=r;++k,--m){
							for(int a=0;a<2;++a)
								for(int b=0;b<2;++b){
									f[i+1][j][k+1][a][b|(k-j+1==y)]+=f[i][j][k][a][b];
								}
						}
					}else{
						for(int k=l,m=i-j-k,o1,o2;k<=r;++k,--m){
							for(int a=0;a<2;++a)
								for(int b=0;b<2;++b){
									f[i+1][j][k][a][b]+=f[i][j][k][a][b];
								}
						}
					}
				}
			ret+=f[n*3][n][n][1][1];
	}
	cout<<ret<<endl;
}
int main() {
	int t,ss;cin>>t>>ss;
	while(t--)solve();
    return 0;
}