#include <bits/stdc++.h>
#define uint unsigned int
#define ull unsigned long long
#define TIME chrono::steady_clock::now().time_since_epoch().count()
using namespace std;
int t,n;
const int K=60;
vector<int> S1,S2;
char s[100101];
char W[11]="ABC";
const int B=801;
uint dp[62][62][40000];
bool ok[61][61][61];
int id[61][61][61],nn,tid[61][61];
// bitset<148840000> F;
inline int HSH(int a,int b,int x,int y,int z)
{
	if(x+y+z>n)return 0;
	return ((n-a)*(n+1)+n-b)*nn+id[x][y][z]+1;
}
ull S,CNT;
int main()
{
	//freopen("abc.in","r",stdin);freopen("force4.out","w",stdout);setvbuf(stdout,0,_IONBF,0);
	scanf("%d%*d",&t);while(t--)
	{
		scanf("%d",&n);
		scanf("%s",s);S1.clear();for(int i=0;i<=n;++i)if(s[i]=='1')S1.push_back(i);
		scanf("%s",s);S2.clear();for(int i=0;i<=n;++i)if(s[i]=='1')S2.push_back(i);
		scanf("%s",s+1);
		int c2=0;
		for(int i=1;i<=3*n;++i)c2+=s[i]=='?';
		if(n!=K)
		{
			puts("-1");
			continue;
		}
		memset(ok,0,sizeof(ok));
		for(int x:S1)for(int y:S2)if(x+y<=n)
		{
			int z=n-x-y;
			ok[x][y][z]=1;
		}
		for(int x=n;~x;--x)for(int y=n;~y;--y)for(int z=n;~z;--z)
		{//printf("x:%d y:%d z:%d\n",x,y,z);
			if(x<n)ok[x][y][z]|=ok[x+1][y][z];
			if(y<n)ok[x][y][z]|=ok[x][y+1][z];
			if(z<n)ok[x][y][z]|=ok[x][y][z+1];
		}
		nn=0;
		for(int x=0;x<=n;++x)for(int y=0;x+y<=n;++y)for(int z=0;x+y+z<=n;++z)id[x][y][z]=nn++;
		for(int x=0;x<=n;++x)for(int y=0;x+y<=n;++y)tid[x][y]=id[x][y][0];
		// printf("nn:%d\n",nn);
		// dp[HSH(0,0,0,0,0)]=1;//F[HSH(0,0,0,0,0)]=1;
		dp[0][0][0]=1;
		// int CNT=0;
		for(int i=0;i<3*n;++i)
		{
			char ch=s[i+1];
			for(int a=min(i,n);~a;--a)
			{
				for(int b=min(i-a,n);~b;--b)
				{
					int c=i-a-b,tt=max(0,c-b);
					if(c>n)continue;
					if(ch=='?')
					{
						// S=TIME;
						for(int x=max(0,a+1-c);x<=a;++x)
						{
							// for(int y=min(b,n-x);y>=max(0,b-a);--y)
							for(int y=max(0,b-a),ii=tid[x][y];y<=min(n-x,b);ii+=n-x-y+1,++y)
							{
								// int ii=tid[x][y];
								for(int z=ii+min(c,n-x-y);z>=ii+tt;--z)
								{
									dp[a+1][b][z]+=dp[a][b][z];
								}
							}
						}
						// CNT+=TIME-S;
						int x=max(0,a-c);
						if(x<max(0,a-c+1))
						{
							for(int y=max(0,b-a);y<=min(n-x-1,b);++y)
							{
								for(int z=min(c,n-x-1-y);z>=tt;--z)
								{
									dp[a+1][b][id[x+1][y][z]]+=dp[a][b][id[x][y][z]];
								}
							}
						}
						for(int x=max(0,a-c);x<=a;++x)
						{
							for(int y=max(0,b-a+1);y<=min(n-x,b);++y)
							{
								int ii=tid[x][y];
								for(int z=ii+min(c,n-x-y);z>=ii+tt;--z)
								{
									dp[a][b+1][z]+=dp[a][b][z];
								}
							}
						}
						int y=max(0,b-a);
						if(y<max(0,b-a+1))
						{
							for(int x=max(0,a-c);x<=a;++x)
							{
								for(int z=min(c,n-x-y-1);z>=tt;--z)
								{
									dp[a][b+1][id[x][y+1][z]]+=dp[a][b][id[x][y][z]];
								}
							}
						}
						for(int x=max(0,a-c);x<=a;++x)
						{
							// for(int y=min(b,n-x);y>=max(0,b-a);--y)
							for(int y=max(0,b-a);y<=min(n-x,b);++y)
							{
								int z=max(0,c-b);
								if(z<max(0,c-b+1)&&z<=c&&x+y+z+1<=n)
								{
									dp[a][b][id[x][y][z+1]]+=dp[a][b][id[x][y][z]];
									dp[a][b][id[x][y][z]]=0;
								}
							}
						}
					}
					else
					{
					// for(int x=a;x>=max(0,a-c);--x)
						if(ch!='B'&&ch!='C')
						{
							for(int x=max(0,a+1-c);x<=a;++x)
							{
								// for(int y=min(b,n-x);y>=max(0,b-a);--y)
								for(int y=max(0,b-a),ii=tid[x][y];y<=min(n-x,b);ii+=n-x-y+1,++y)
								{
									// int ii=tid[x][y];
									for(int z=ii+min(c,n-x-y);z>=ii+tt;--z)
									{
										dp[a+1][b][z]+=dp[a][b][z];
									}
								}
							}
							// CNT+=TIME-S;
							int x=max(0,a-c);
							if(x<max(0,a-c+1))
							{
								for(int y=max(0,b-a);y<=min(n-x-1,b);++y)
								{
									for(int z=min(c,n-x-1-y);z>=tt;--z)
									{
										dp[a+1][b][id[x+1][y][z]]+=dp[a][b][id[x][y][z]];
									}
								}
							}
						}
						if(ch!='C'&&ch!='A')
						{
							for(int x=max(0,a-c);x<=a;++x)
							{
								for(int y=max(0,b-a+1);y<=min(n-x,b);++y)
								{
									int ii=tid[x][y];
									for(int z=ii+min(c,n-x-y);z>=ii+tt;--z)
									{
										dp[a][b+1][z]+=dp[a][b][z];
									}
								}
							}
							int y=max(0,b-a);
							if(y<max(0,b-a+1))
							{
								for(int x=max(0,a-c);x<=a;++x)
								{
									for(int z=min(c,n-x-y-1);z>=tt;--z)
									{
										dp[a][b+1][id[x][y+1][z]]+=dp[a][b][id[x][y][z]];
									}
								}
							}
						}
						if(ch=='A'||ch=='B')
						{
							for(int x=max(0,a-c);x<=a;++x)
							{
								// for(int y=min(b,n-x);y>=max(0,b-a);--y)
								for(int y=max(0,b-a);y<=min(n-x,b);++y)
								{
									for(int z=min(c,n-x-y);z>=tt;--z)
									{
										dp[a][b][id[x][y][z]]=0;
									}
								}
							}
						}
						else
						{
							for(int x=max(0,a-c);x<=a;++x)
							{
								// for(int y=min(b,n-x);y>=max(0,b-a);--y)
								for(int y=max(0,b-a);y<=min(n-x,b);++y)
								{
									int z=max(0,c-b);
									if(z<max(0,c-b+1)&&z<=c&&x+y+z+1<=n)
									{
										dp[a][b][id[x][y][z+1]]+=dp[a][b][id[x][y][z]];
										dp[a][b][id[x][y][z]]=0;
									}
								}
							}
						}
					}

				}
			}
		}
		// printf("CNT:%d\n",CNT);
		uint ans=0;
		for(int x=0;x<=n;++x)for(int y=0;x+y<=n;++y)for(int z=0;x+y+z<=n;++z)ans+=dp[n][n][id[x][y][z]]*ok[x][y][z];
		printf("%u\n",ans);
		//printf("CNT:%.9lfs\n",CNT/1e9);
	}
	fclose(stdin);fclose(stdout);return 0;
}