#include<bits/stdc++.h>
using namespace std;
const int N=185;
char a[N],s1[N],s2[N];
int T,cas,n,nxta[N],nxtb[N];
unsigned dp[4][61][61],qwq[4][61][61];
int main(){
    // freopen("qwq.in","r",stdin);
    // freopen("qwq.out","w",stdout);
    int B=58;
    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;
            }
            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];
            }
            unsigned 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[(la==0)+(la==0)+(lb==0)][0][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;j<i&&j<n;++j)for(register int k=0,w=i-1-j;k<i&&k<=n;++k,--w){
                                if(j+1-w<=la){
                                    if(qwq[0][j][k])dp[(j+1-w==la)<<1][j+1][k]+=qwq[0][j][k];
                                    if(qwq[1][j][k])dp[(j+1-w==la)<<1|1][j+1][k]+=qwq[1][j][k];
                                    if(qwq[2][j][k])dp[2][j+1][k]+=qwq[2][j][k];
                                    if(qwq[3][j][k])dp[3][j+1][k]+=qwq[3][j][k];
                                }
                            }
                        }
                        else if(a[i]=='B'){
                            for(register int j=0;j<i&&j<=n;++j)for(register int k=0,w=i-1-j;k<i&&k<n;++k,--w){
                                if(k+1-j<=lb){
                                    if(qwq[0][j][k])dp[k+1-j==lb][j][k+1]+=qwq[0][j][k];
                                    if(qwq[1][j][k])dp[1][j][k+1]+=qwq[1][j][k];
                                    if(qwq[2][j][k])dp[2^(k+1-j==lb)][j][k+1]+=qwq[2][j][k];
                                    if(qwq[3][j][k])dp[3][j][k+1]+=qwq[3][j][k];
                                }
                            }
                        }
                        else if(a[i]=='C'){
                            for(register int j=0;j<i&&j<=n;++j)for(register int k=0,w=i-1-j;k<i&&k<=n;++k,--w){
                                if(w<n&&w+1-k<=lc){
                                    if(qwq[0][j][k])dp[0][j][k]+=qwq[0][j][k];
                                    if(qwq[1][j][k])dp[1][j][k]+=qwq[1][j][k];
                                    if(qwq[2][j][k])dp[2][j][k]+=qwq[2][j][k];
                                    if(qwq[3][j][k])dp[3][j][k]+=qwq[3][j][k];
                                }
                            }
                        }
                        else{
                            for(register int j=0;j<i&&j<=n;++j)for(register int k=0,w=i-1-j;k<i&&k<=n;++k,--w){
                                if(qwq[0][j][k]){
                                    if(j<n&&j+1-w<=la)dp[(j+1-w==la)<<1][j+1][k]+=qwq[0][j][k];
                                    if(k<n&&k+1-j<=lb)dp[k+1-j==lb][j][k+1]+=qwq[0][j][k];
                                    if(w<n&&w+1-k<=lc)dp[0][j][k]+=qwq[0][j][k];
                                }
                                if(qwq[1][j][k]){
                                    if(j<n&&j+1-w<=la)dp[(j+1-w==la)<<1|1][j+1][k]+=qwq[1][j][k];
                                    if(k<n&&k+1-j<=lb)dp[1][j][k+1]+=qwq[1][j][k];
                                    if(w<n&&w+1-k<=lc)dp[1][j][k]+=qwq[1][j][k];
                                }
                                if(qwq[2][j][k]){
                                    if(j<n&&j+1-w<=la)dp[2][j+1][k]+=qwq[2][j][k];
                                    if(k<n&&k+1-j<=lb)dp[2^(k+1-j==lb)][j][k+1]+=qwq[2][j][k];
                                    if(w<n&&w+1-k<=lc)dp[2][j][k]+=qwq[2][j][k];
                                }
                                if(qwq[3][j][k]){
                                    if(j<n&&j+1-w<=la)dp[3][j+1][k]+=qwq[3][j][k];
                                    if(k<n&&k+1-j<=lb)dp[3][j][k+1]+=qwq[3][j][k];
                                    if(w<n&&w+1-k<=lc)dp[3][j][k]+=qwq[3][j][k];
                                }
                            }
                        }
                    }
                    ans+=dp[3][n][n];
                }
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}