#include<bits/stdc++.h>

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

#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);
}


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);
    if(opt==3)rotate(a,b,c),rotate(x,y,z);
    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[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=check(a,b,c,1,X.se,Y.fi);
                    int flag2=check(a,b,c,1,X.fi,Y.se),flag3=check(a,b,c,1,X.se,Y.se);
                    if(flag0)f[0][a+1][b][c]+=f[0][a][b][c];
                    if((~X.se) && X.se+Y.fi<=n && flag0 && flag1)f[1][a+1][b][c]+=f[1][a][b][c];
                    if((~Y.se) && X.fi+Y.se<=n && flag0 && flag2)f[2][a+1][b][c]+=f[2][a][b][c];
                    if((~Y.se) && (~X.se) && X.se+Y.se<=n && flag0 && flag2 && flag1 && flag3)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=check(a,b,c,2,X.se,Y.fi);
                    int flag2=check(a,b,c,2,X.fi,Y.se),flag3=check(a,b,c,2,X.se,Y.se);
                    if(flag0)f[0][a][b+1][c]+=f[0][a][b][c];
                    if((~X.se) && X.se+Y.fi<=n && flag0 && flag1)f[1][a][b+1][c]+=f[1][a][b][c];
                    if((~Y.se) && X.fi+Y.se<=n && flag0 && flag2)f[2][a][b+1][c]+=f[2][a][b][c];
                    if((~Y.se) && (~X.se) && X.se+Y.se<=n && flag0 && flag2 && flag1 && flag3)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=check(a,b,c,3,X.se,Y.fi);
                    int flag2=check(a,b,c,3,X.fi,Y.se),flag3=check(a,b,c,3,X.se,Y.se);
                    if(flag0)f[0][a][b][c+1]+=f[0][a][b][c];
                    if((~X.se) && X.se+Y.fi<=n && flag0 && flag1)f[1][a][b][c+1]+=f[1][a][b][c];
                    if((~Y.se) && X.fi+Y.se<=n && flag0 && flag2)f[2][a][b][c+1]+=f[2][a][b][c];
                    if((~Y.se) && (~X.se) && X.se+Y.se<=n && flag0 && flag2 && flag1 && flag3)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;
}