#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int ll;
const int N=185;
char a[N],s1[N],s2[N];
int T,cas,n,nxta[N],nxtb[N];
ll dp[62][62][2][2],qwq[62][62][2][2];
int main(){
    // freopen("qwq.in","r",stdin);
    // freopen("qwq.out","w",stdout);
    int B=59;
    for(cin>>T>>cas;T;T--){
        scanf("%d%s%s%s",&n,s1,s2,a+1);
        if(cas<=2){
            int n1=0,n2=0,n3=0,ca=0,cb=0,cc=0;
            for(int i=1;i<=3*n;i++){
                if(a[i]=='A')n1++,n2--;
                if(a[i]=='B')n2++,n3--;
                if(a[i]=='C')n3++,n1--;
                ca=max(ca,n1);
                cb=max(cb,n2);
                cc=max(cc,n3);
            }
            if(ca+cb+cc>n){
                puts("0");continue;
            }
            bool flag=0;
            for(int i=ca;i+cb+cc<=n;i++)if(s1[i]=='1'){
                for(int j=cb;i+j+cc<=n;j++){
                    if(s2[j]=='1')flag=1;
                }
            }
            puts(flag?"1":"0");
        }
        else if(cas<=3){
            puts(n==60?"2103642368":"-1");
        }
        else{
            if(n!=B){
                puts("-1");continue;
            }
            nxta[n+1]=n+1,nxtb[n+1]=n+1;
            for(int i=n;i>=0;i--){
                if(s1[i]=='1')nxta[i]=i;
                else nxta[i]=nxta[i+1];
                if(s2[i]=='1')nxtb[i]=i;
                else nxtb[i]=nxtb[i+1];
            }
            ll ans=0;
            for(int la=0;la<=n;la++){
                for(int lb=0;la+lb<=n;lb++){
                    int lc=n-nxta[la]-nxtb[lb];
                    if(lc<0)continue;
                    memset(dp,0,sizeof dp);
                    dp[0][0][la==0][lb==0]=1;
                    for(int i=1;i<=3*n;i++){
                        memcpy(qwq,dp,sizeof qwq);
                        memset(dp,0,sizeof dp);
                        int j,k,w;
                        if(a[i]=='A'){  
                            for(j=0;j<i&&j<60;++j)for(k=0,w=i-1-j;k<i&&k<=60;++k,--w){
                                if(j+1-w<=la){
                                    auto qaq=qwq[j][k];
                                    if(qaq[0][0])dp[j+1][k][j+1-w==la][0]+=qaq[0][0];
                                    if(qaq[0][1])dp[j+1][k][j+1-w==la][1]+=qaq[0][1];
                                    if(qaq[1][0])dp[j+1][k][1][0]+=qaq[1][0];
                                    if(qaq[1][1])dp[j+1][k][1][1]+=qaq[1][1];
                                }
                            }
                        }
                        else if(a[i]=='B'){
                            for(j=0;j<i&&j<=60;++j)for(k=0,w=i-1-j;k<i&&k<60;++k,--w){
                                if(k+1-j<=lb){
                                    auto qaq=qwq[j][k];
                                    if(qaq[0][0])dp[j][k+1][0][k+1-j==lb]+=qaq[0][0];
                                    if(qaq[0][1])dp[j][k+1][0][1]+=qaq[0][1];
                                    if(qaq[1][0])dp[j][k+1][1][k+1-j==lb]+=qaq[1][0];
                                    if(qaq[1][1])dp[j][k+1][1][1]+=qaq[1][1];
                                }
                            }
                        }
                        else if(a[i]=='C'){
                            for(j=0;j<i&&j<=60;++j)for(k=0,w=i-1-j;k<i&&k<=60;++k,--w){
                                if(w<60&&w+1-k<=lc){
                                    auto qaq=qwq[j][k];
                                    if(qaq[0][0])dp[j][k][0][0]+=qaq[0][0];
                                    if(qaq[0][1])dp[j][k][0][1]+=qaq[0][1];
                                    if(qaq[1][0])dp[j][k][1][0]+=qaq[1][0];
                                    if(qaq[1][1])dp[j][k][1][1]+=qaq[1][1];
                                }
                            }
                        }
                        else{
                            for(j=0;j<i&&j<=60;++j)for(k=0,w=i-1-j;k<i&&k<=60;++k,--w){
                                auto qaq=qwq[j][k];
                                bool ok1=j+1-w<=la,ok2=k+1-j<=lb,ok3=w+1-k<=lc;
                                if(qaq[0][0]){
                                    if(ok1)dp[j+1][k][j+1-w==la][0]+=qaq[0][0];
                                    if(ok2)dp[j][k+1][0][k+1-j==lb]+=qaq[0][0];
                                    if(ok3)dp[j][k][0][0]+=qaq[0][0];
                                }
                                if(qaq[0][1]){
                                    if(ok1)dp[j+1][k][j+1-w==la][1]+=qaq[0][1];
                                    if(ok2)dp[j][k+1][0][1]+=qaq[0][1];
                                    if(ok3)dp[j][k][0][1]+=qaq[0][1];
                                }
                                if(qaq[1][0]){
                                    if(ok1)dp[j+1][k][1][0]+=qaq[1][0];
                                    if(ok2)dp[j][k+1][1][k+1-j==lb]+=qaq[1][0];
                                    if(ok3)dp[j][k][1][0]+=qaq[1][0];
                                }
                                if(qaq[1][1]){
                                    if(ok1)dp[j+1][k][1][1]+=qaq[1][1];
                                    if(ok2)dp[j][k+1][1][1]+=qaq[1][1];
                                    if(ok3)dp[j][k][1][1]+=qaq[1][1];
                                }
                            }
                        }
                    }
                    ans+=dp[n][n][1][1];
                }
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}