#include<bits/stdc++.h>

#define uint unsigned int
#define pi pair<uint,uint>
#define vi vector<uint>
#define cpy(x,y,s) memcpy(x,y,sizeof(x[0])*(s))
#define mset(x,v,s) memset(x,v,sizeof(x[0])*(s))
#define all(x) begin(x),end(x)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ary array
#define IL inline

#define N 62

using namespace std;
uint read(){
    uint x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9')f=(ch=='-'?-1:f),ch=getchar();
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
void write(uint x){
    if(x<0)x=-x,putchar('-');
    if(x/10)write(x/10);
    putchar(x%10+'0');
}

char A[N*3],B[N*3],s[N*3];
uint n,m;

IL void rotate(uint &a,uint &b,uint &c){
    a=a^b;b=a^b;a=a^b;b=b^c;c=b^c;b=b^c;
}
IL void Rotate(uint &a,uint &b,uint &c){
    a=a^b;b=a^b;a=a^b;a=a^c;c=a^c;a=a^c;
}


IL bool check(uint a,uint b,uint c,uint opt,uint x,uint y){
    if(!(~x) || !(~y))return true;
    uint z=n-x-y;
    if(opt==2)rotate(a,b,c),rotate(x,y,z);
    else if(opt==3)Rotate(a,b,c),Rotate(x,y,z);
    return (a+1<=x?(true):((a+1<=x+z)?((a+1-x<=c)?true:false):((b>=a+1-x-z && c-z>=a+1-x-z)?true:false)));
}

uint f[4][N][N][N];
IL uint dp(pi X,pi Y){
    if(X.fi+Y.fi>n)return 0;
    uint res=0;
    memset(f,0,sizeof(f));
    f[0][0][0][0]=1;
    if(~(X.se))f[1][0][0][0]=1;
    if(~(Y.se))f[2][0][0][0]=1;
    if((~X.se) && (~Y.se))f[3][0][0][0]=1;
    for(uint i=1;i<=m;i++){
        int lim=min(i-1,n);
        for(uint a=0;a<=lim;a++){
            int lim=min(i-1,n+a);
            for(uint b=0;b+a<=lim;b++){
                uint c=i-1-a-b;
                if(c>n || !f[a][b][c])continue;
                if(a!=n && (s[i]=='A' || s[i]=='?')){
                    int flag0=check(a,b,c,1,X.fi,Y.fi),flag1,flag2,flag3;
                    if(flag0)f[0][a+1][b][c]+=f[0][a][b][c];
                    if((~X.se) && X.se+Y.fi<=n && flag0){
                        if(flag1=check(a,b,c,1,X.se,Y.fi))f[1][a+1][b][c]+=f[1][a][b][c];
                    }
                    if((~Y.se) && X.fi+Y.se<=n && flag0){
                        if(flag2=check(a,b,c,1,X.fi,Y.se))f[2][a+1][b][c]+=f[2][a][b][c];
                    }
                    if((~Y.se) && (~X.se) && X.se+Y.se<=n && flag0 && flag2 && flag1){
                        if(flag3=check(a,b,c,1,X.se,Y.se))f[3][a+1][b][c]+=f[3][a][b][c];
                    }
                }
                if(b!=n && (s[i]=='B' || s[i]=='?')){
                    int flag0=check(a,b,c,2,X.fi,Y.fi),flag1,flag2,flag3;
                    if(flag0)f[0][a][b+1][c]+=f[0][a][b][c];
                    if((~X.se) && X.se+Y.fi<=n && flag0){
                        if(flag1=check(a,b,c,2,X.se,Y.fi))f[1][a][b+1][c]+=f[1][a][b][c];
                    }
                    if((~Y.se) && X.fi+Y.se<=n && flag0){
                        if(flag2=check(a,b,c,2,X.fi,Y.se))f[2][a][b+1][c]+=f[2][a][b][c];
                    }
                    if((~Y.se) && (~X.se) && X.se+Y.se<=n && flag0 && flag2 && flag1){
                        if(flag3=check(a,b,c,2,X.se,Y.se))f[3][a][b+1][c]+=f[3][a][b][c];
                    }
                }
                if(c!=n && (s[i]=='C' || s[i]=='?')){
                    int flag0=check(a,b,c,3,X.fi,Y.fi),flag1,flag2,flag3;
                    if(flag0)f[0][a][b][c+1]+=f[0][a][b][c];
                    if((~X.se) && X.se+Y.fi<=n && flag0){
                        if(flag1=check(a,b,c,3,X.se,Y.fi))f[1][a][b][c+1]+=f[1][a][b][c];
                    }
                    if((~Y.se) && X.fi+Y.se<=n && flag0){
                        if(flag2=check(a,b,c,3,X.fi,Y.se))f[2][a][b][c+1]+=f[2][a][b][c];
                    }
                    if((~Y.se) && (~X.se) && X.se+Y.se<=n && flag0 && flag2 && flag1){
                        if(flag3=check(a,b,c,3,X.se,Y.se))f[3][a][b][c+1]+=f[3][a][b][c];
                    }
                }
            }
        }
    }
    return f[0][n][n][n]-f[1][n][n][n]-f[2][n][n][n]+f[3][n][n][n];
}
void solve(){
    uint res=0;m=3*n;
    vi S,T;
    for(uint i=1;i<=n+1;i++){
        if(A[i]=='1')S.pb(i-1);
        if(B[i]=='1')T.pb(i-1);
    }
    for(uint i=0;i<S.size();i++){
        pi X=mp(S[i],(i+1<S.size()?S[i+1]:-1));
        for(int j=0;j<T.size();j++){
            pi Y=mp(T[j],(j+1<T.size()?T[j+1]:-1));
            res+=dp(X,Y);
        }
    }
    write(res);putchar('\n');
}

int main(){
    #ifdef EAST_CLOUD
    freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    #endif

    uint T=read(),c=read();
    for(uint i=1;i<=T;i++){
        n=read();
        scanf("%s",A+1);scanf("%s",B+1);scanf("%s",s+1);
        if(i!=50){cout<<-1<<endl;continue;}
        solve();
    }
    return 0;
}