#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){
    swap(a,b);swap(b,c);
}

int debug=0;

IL bool check(uint a,uint b,uint c,uint opt,uint x,uint y){
    uint z=n-x-y;
    //if(debug)cerr<<a<<' '<<b<<' '<<c<<' '<<x<<' '<<y<<' '<<z<<endl;
    if(opt>=2)rotate(a,b,c),rotate(x,y,z);
    if(opt==3)rotate(a,b,c),rotate(x,y,z);
    //if(debug)cerr<<a<<' '<<b<<' '<<c<<' '<<x<<' '<<y<<' '<<z<<endl;
    if(a+1<=x)return true;
    else if(a+1<=x+z){
        if(a+1-x<=c)return true;
        return false;
    }
    else{
        if(b>=a+1-x-z && c-z>=a+1-x-z)return true;
        return false;
    }
}
IL bool che(uint a,uint b,uint c,uint opt,pi X,pi Y){
    if((~X.fi) && (~Y.fi) && !check(a,b,c,opt,X.fi,Y.fi))return false;
    if((~X.fi) && (~Y.se) && !check(a,b,c,opt,X.fi,Y.se))return false;
    if((~X.se) && (~Y.fi) && !check(a,b,c,opt,X.se,Y.fi))return false;
    if((~X.se) && (~Y.se) && !check(a,b,c,opt,X.se,Y.se))return false;
    return true;
}

uint f[N][N][N];
IL uint dp(pi X,pi Y){
    uint res=0;
    memset(f,0,sizeof(f));f[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]=='?') && che(a,b,c,1,X,Y))f[a+1][b][c]+=f[a][b][c];
                if(b!=n && (s[i]=='B' || s[i]=='?') && che(a,b,c,2,X,Y))f[a][b+1][c]+=f[a][b][c];
                if(c!=n && (s[i]=='C' || s[i]=='?') && che(a,b,c,3,X,Y))f[a][b][c+1]+=f[a][b][c];
            }
        }
    }
    return f[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],-1);
        for(uint j=0;j<T.size();j++){
            if(S[i]+T[j]>n)break;
            pi Y=mp(T[j],-1);
            uint tmp=dp(X,Y);res+=tmp;
        }
        for(uint j=0;j<T.size()-1;j++){
            if(S[i]+T[j+1]>n)break;
            pi Y=mp(T[j],T[j+1]);
            uint tmp=dp(X,Y);res-=tmp;
        }
    }
    for(uint i=0;i<S.size()-1;i++){
        pi X=mp(S[i],S[i+1]);
        for(uint j=0;j<T.size();j++){
            if(S[i+1]+T[j]>n)break;
            pi Y=mp(T[j],-1);
            res-=dp(X,Y);
        }
        for(uint j=0;j<T.size()-1;j++){
            if(S[i+1]+T[j+1]>n)break;
            pi Y=mp(T[j],T[j+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;
}