#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
typedef unsigned int ll;
typedef unsigned long long ull;
#define MP make_pair
#define pii pair<int,int>
const double PI=acos(-1.0);
template <class Miaowu>
inline void in(Miaowu &x){
    char c;x=0;bool f=0;
    for(c=getchar();c<'0'||c>'9';c=getchar())f|=c=='-';
    for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
    x=f?-x:x;
}
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];
long long F[2][2][62][62];
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(n!=B){
                puts("-1");continue;
            }
            memset(F,-1,sizeof F);
            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;
                    if(F[la==0][lb==0][nxta[la]][nxtb[lb]]!=-1){
                        ans+=F[la==0][lb==0][nxta[la]][nxtb[lb]];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);
                        if(a[i]=='A'){
                            for(register int j=0,l1=1-la;j<i&&j<n;++j,++l1)for(register int k=0,w=i-1-j;k<i&&k<=n&&w>=l1;++k,--w){
                                if(qwq[j][k][0][0])dp[j+1][k][j+1-w==la][0]+=qwq[j][k][0][0];
                                if(qwq[j][k][0][1])dp[j+1][k][j+1-w==la][1]+=qwq[j][k][0][1];
                                if(qwq[j][k][1][0])dp[j+1][k][1][0]+=qwq[j][k][1][0];
                                if(qwq[j][k][1][1])dp[j+1][k][1][1]+=qwq[j][k][1][1];
                            }
                        }
                        else if(a[i]=='B'){
                            for(register int j=0,l2=lb-1;j<i&&j<=n;++j,++l2)for(register int k=0;k<i&&k<n&&k<=l2;++k){
                                if(qwq[j][k][0][0])dp[j][k+1][0][k+1-j==lb]+=qwq[j][k][0][0];
                                if(qwq[j][k][0][1])dp[j][k+1][0][1]+=qwq[j][k][0][1];
                                if(qwq[j][k][1][0])dp[j][k+1][1][k+1-j==lb]+=qwq[j][k][1][0];
                                if(qwq[j][k][1][1])dp[j][k+1][1][1]+=qwq[j][k][1][1];
                            }
                        }
                        else if(a[i]=='C'){
                            for(register int j=0;j<i&&j<=n;++j)for(register int k=max(max(i-j-n,0),(i-j-lc+1)/2),w=i-1-j-k;k<i&&k<=n;++k,--w){
                                if(qwq[j][k][0][0])dp[j][k][0][0]+=qwq[j][k][0][0];
                                if(qwq[j][k][0][1])dp[j][k][0][1]+=qwq[j][k][0][1];
                                if(qwq[j][k][1][0])dp[j][k][1][0]+=qwq[j][k][1][0];
                                if(qwq[j][k][1][1])dp[j][k][1][1]+=qwq[j][k][1][1];
                            }
                        }
                        else{
                            for(register int j=0,l1=1-la,l2=lb-1;j<i&&j<=n;++j,++l1,++l2)for(register int k=0,w=i-1-j,l3=lc-1;k<i&&k<=n;++k,--w,++l3){
                                auto qaq=qwq[j][k];
                                if(qaq[0][0]){
                                    if(w>=l1)dp[j+1][k][w==l1][0]+=qaq[0][0];
                                    if(k<=l2)dp[j][k+1][0][k==l2]+=qaq[0][0];
                                    if(w<=l3)dp[j][k][0][0]+=qaq[0][0];
                                }
                                if(qaq[0][1]){
                                    if(w>=l1)dp[j+1][k][w==l1][1]+=qaq[0][1];
                                    if(k<=l2)dp[j][k+1][0][1]+=qaq[0][1];
                                    if(w<=l3)dp[j][k][0][1]+=qaq[0][1];
                                }
                                if(qaq[1][0]){
                                    if(w>=l1)dp[j+1][k][1][0]+=qaq[1][0];
                                    if(k<=l2)dp[j][k+1][1][k==l2]+=qaq[1][0];
                                    if(w<=l3)dp[j][k][1][0]+=qaq[1][0];
                                }
                                if(qaq[1][1]){
                                    if(w>=l1)dp[j+1][k][1][1]+=qaq[1][1];
                                    if(k<=l2)dp[j][k+1][1][1]+=qaq[1][1];
                                    if(w<=l3)dp[j][k][1][1]+=qaq[1][1];
                                }
                            }
                        }
                    }
                    ans+=dp[n][n][1][1];
                    F[la==0][lb==0][nxta[la]][nxtb[lb]]=dp[n][n][1][1];
                }
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}