#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ui=unsigned int;
const int N=65;
int type,n,v1[N],v2[N];
ui f[N][N][N][2][2];
string s1,s2,a;
void solve() {
    cin>>n>>s1>>s2>>a,a=' '+a;
    if(n!=60)return cout<<"-1\n",void();
    v1[n+1]=v2[n+1]=n+1;
    for(int i=n;~i;i--)v1[i]=(s1[i]=='1'?i:v1[i+1]),v2[i]=(s2[i]=='1'?i:v2[i+1]);
    ui ans=0;
    for(int x=0;x<=n;x++)for(int y=0;x+y<=n;y++)if(s1[x]=='1'&&s2[y]=='1') {
        memset(f,0,sizeof(f)),f[0][0][0][v1[0]==x][v2[0]==y]=1;
        for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)if(j-i<=y)for(int k=0;k<=n;k++)if(i-k<=x&&i+j+k!=3*n)
            for(int p=0;p<2;p++)for(int q=0;q<2;q++)if(f[i][j][k][p][q]) {
                if((a[i+j+k+1]=='?'||a[i+j+k+1]=='A')&&v1[i+1-k]<=x)f[i+1][j][k][(v1[i+1-k]==x)|p][q]+=f[i][j][k][p][q];
                if((a[i+j+k+1]=='?'||a[i+j+k+1]=='B')&&v2[j+1-i]<=y)f[i][j+1][k][p][(v2[j+1-i]==y)|q]+=f[i][j][k][p][q];
                if((a[i+j+k+1]=='?'||a[i+j+k+1]=='C')&&k+1-j<=n-y-x)f[i][j][k+1][p][q]+=f[i][j][k][p][q];
            }
        ans+=f[n][n][n][1][1];
    }cout<<ans<<'\n';
}
int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int tt;cin>>tt>>type;
    while(tt--)solve();
    return 0;
}