#include <bits/stdc++.h>
using namespace std;

const int N=65;

char S1[N], S2[N], s[N*3];
bool have[N][N][N];
unsigned int dp[N][N][N], ans[N][N][N];
int nexpos1[N], nexpos2[N], n;

unsigned int calc(int x,int y,int z)
{
	if(have[x][y][z])
		return ans[x][y][z];

	memset(dp,0,sizeof(dp));
	dp[0][0][0]=1;
	for(register int a=0;a<=n;a++)
		for(register int b=0;b<=n;b++)
			for(register int c=0;c<=n;c++)
			{
				int val=dp[a][b][c], id=a+b+c+1;
				if(val)
				{
					if(a<n && a+1-c<=x && (s[id]=='A' || s[id]=='?'))
						dp[a+1][b][c] += dp[a][b][c];

					if(b<n && b+1-a<=y && (s[id]=='B' || s[id]=='?'))
						dp[a][b+1][c] += dp[a][b][c];

					if(c<n && c+1-b<=z && (s[id]=='C' || s[id]=='?'))
						dp[a][b][c+1] += dp[a][b][c];
				}
			}

	have[x][y][z]=true;
	ans[x][y][z]=dp[n][n][n];
	return dp[n][n][n];
}

void work()
{
	scanf("%d",&n);
	scanf("%s",S1);
	scanf("%s",S2);
	scanf("%s",s+1);
	if(n!=60)
	{
		printf("-1\n");
		return;
	}

	nexpos1[n+1]=n+1;
	for(int i=n;i>=0;i--)
		if(S1[i]=='1')
			nexpos1[i]=i;
		else
			nexpos1[i]=nexpos1[i+1];

	nexpos2[n+1]=n+1;
	for(int i=n;i>=0;i--)
		if(S2[i]=='1')
			nexpos2[i]=i;
		else
			nexpos2[i]=nexpos2[i+1];

	unsigned int ans=0;
	for(int x=0;x<=n;x++)
		for(int y=0;y<=n;y++)
			if(nexpos1[x]+nexpos2[y]<=n)
				ans += calc(x,y,n-nexpos1[x]-nexpos2[y])-calc(x-1,y,n-nexpos1[x]-nexpos2[y])-calc(x,y-1,n-nexpos1[x]-nexpos2[y])+calc(x-1,y-1,n-nexpos1[x]-nexpos2[y]);
	printf("%u\n",ans);
}

int main()
{
	int T,c;
	cin >> T >> c;
	while(T--)
		work();
	return 0;
}