// created:  2024-10-15 08:28:28
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define F(i,l,r) for(int i=(l),i##_end=(r);i<i##_end;++i)
#define I128 //||is_same<T,__int128_t>::value||is_same<T,__uint128_t>::value
using namespace std;
template<typename T>enable_if_t<is_integral<T>::value I128,void> readmain(T &x)
{
	bool neg=false;int c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')neg=true;
	for(x=0;isdigit(c);c=getchar())x=(T)(10*x+(c-'0'));
	if(neg)x=-x;
}
template<typename T>T& read(T &x){readmain(x);return x;}
template<typename T,typename ...Tr>void read(T &x,Tr&... r){readmain(x);read(r...);}
typedef unsigned uint;
constexpr int N=63,M=2e7;
constexpr char answer[6][61]=
{
"111111111111111111111111111111111111111111111111111111111111",
"111111111111111111111111111111111111111111111111111111111111",
"111111111111111111111111111111111111111111111111111111111111",
"000000000000000000000000000000000000000000000000000000000001",
"000000000000000000000000000000000000000000000000000000000100",
"000000000000000000000000000000000000000000000000000000000100",
};
struct array5
{
	uint *f[N][N][N][N],ff[M];
	void alloc(int n,int i)
	{
		uint *ptr=ff+n+1;
		F(b,0,min(i,n+1)+1)
		{
			F(c,0,min(i-b,n+1)+1)
			{
				int a=i-b-c;if(a<0||a>n+1)continue;
				F(d0,max(a-c,0),a+1)
				{
					F(d1,max(b-a,0),min(b,n-d0+1)+1)
					{
						int d2min=max(c-b,0),d2max=min(c,n-d0-d1+1)+1;
						if(d2min<d2max)
						{
							f[b][c][d0][d1]=ptr-=d2min;
							ptr+=d2max;
						}
					}
				}
			}
		}
		memset(ff,0,sizeof(uint)*(ptr-ff));
	}
	uint &get(int b,int c,int d0,int d1,int d2){return f[b][c][d0][d1][d2];}
};
int id,n;
uint ans;
array5 ff[2],*f,*g;
char s[3*N],s1[N],s2[N];
void input()
{
	read(n);
	scanf("%s%s%s",s1,s2,s);
}
bool chk(int d0,int d1,int d2)
{
	F(i,d0,n+1)F(j,d1,n-i-d2+1)if(s1[i]=='1'&&s2[j]=='1')return true;
	return false;
}
void solve()
{
	bool q=false,sp=true;
	F(i,0,3*n)if(s[i]=='?')q=true;
	else sp=false;
	F(i,0,n+1)if(s1[i]=='0'||s2[i]=='0')sp=false;
	if(sp&&n==60)
	{
		ans=2103642368;
		return;
	}
	if(!q)
	{
		int a=0,b=0,c=0,d0=0,d1=0,d2=0;
		F(i,0,3*n)
		{
			if(s[i]=='A')++a,d0=max(d0,a-c);
			if(s[i]=='B')++b,d1=max(d1,b-a);
			if(s[i]=='C')++c,d2=max(d2,c-b);
		}
		bool ok=false;
		if(a==n&&b==n&&c==n)ok=chk(d0,d1,d2);
		ans=ok;
		return;
	}
	f=ff;g=ff+1;
	f->alloc(n,0);
	f->get(0,0,0,0,0)=1;
	F(i,0,3*n)
	{
		int tp=s[i]=='?'?7:1<<(s[i]-'A');
		g->alloc(n,i+1);
		F(b,0,min(i,n)+1)
		{
			F(c,0,min(i-b,n)+1)
			{
				int a=i-b-c;if(a<0||a>n)continue;
				F(d0,max(a-c,0),a+1)
				{
					F(d1,max(b-a,0),min(b,n-d0)+1)
					{
						F(d2,max(c-b,0),min(c,n-d0-d1)+1)
						{
							if(tp&1)g->get(b,c,max(d0,a+1-c),d1,d2)+=f->get(b,c,d0,d1,d2);
							if(tp&2)g->get(b+1,c,d0,max(d1,b+1-a),d2)+=f->get(b,c,d0,d1,d2);
							if(tp&4)g->get(b,c+1,d0,d1,max(d2,c+1-b))+=f->get(b,c,d0,d1,d2);
						}
					}
				}
			}
		}
		swap(f,g);
	}
	ans=0;
	F(d0,0,n+1)F(d1,0,n-d0+1)F(d2,0,n-d0-d1+1)if(chk(d0,d1,d2))ans+=f->get(n,n,d0,d1,d2);
}
int main()
{
	int tt;
	read(tt,id);
#ifdef LOCAL
	id=0;
#endif
	for(int i=0;i<tt;++i)
	{
		input();
		if(answer[id][i]=='1')solve(),printf("%u\n",ans);
		else puts("-1");
	}
	return 0;
}