#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];
int main(){
    // freopen("qwq.in","r",stdin);
    // freopen("qwq.out","w",stdout);
    int B=57;
    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];
            }
            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);
                        if(a[i]=='A'){
                            for(int j=0;j<i&&j<=n;j++)for(int k=0,w=i-1-j;k<i&&k<=n;k++,w--)for(int oa:{0,1})for(int ob:{0,1}){
                                if(qwq[j][k][oa][ob]&&j<n&&j+1-w<=la)dp[j+1][k][oa|(j+1-w==la)][ob]+=qwq[j][k][oa][ob];
                            }
                        }
                        else if(a[i]=='B'){
                            for(int j=0;j<i&&j<=n;j++)for(int k=0;k<i&&k<=n;k++)for(int oa:{0,1})for(int ob:{0,1}){
                                if(qwq[j][k][oa][ob]&&k<n&&k+1-j<=lb)dp[j][k+1][oa][ob|(k+1-j==lb)]+=qwq[j][k][oa][ob];
                            }
                        }
                        else if(a[i]=='C'){
                            for(int j=0;j<i&&j<=n;j++)for(int k=0,w=i-1-j;k<i&&k<=n;k++,w--)for(int oa:{0,1})for(int ob:{0,1}){
                                if(qwq[j][k][oa][ob]&&w<n&&w+1-k<=lc)dp[j][k][oa][ob]+=qwq[j][k][oa][ob];
                            }
                        }
                        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[j][k][0][0]){
                                    if(j<n&&j+1-w<=la)dp[j+1][k][j+1-w==la][0]+=qwq[j][k][0][0];
                                    if(k<n&&k+1-j<=lb)dp[j][k+1][0][k+1-j==lb]+=qwq[j][k][0][0];
                                    if(w<n&&w+1-k<=lc)dp[j][k][0][0]+=qwq[j][k][0][0];
                                }
                                if(qwq[j][k][0][1]){
                                    if(j<n&&j+1-w<=la)dp[j+1][k][j+1-w==la][1]+=qwq[j][k][0][1];
                                    if(k<n&&k+1-j<=lb)dp[j][k+1][0][1]+=qwq[j][k][0][1];
                                    if(w<n&&w+1-k<=lc)dp[j][k][0][1]+=qwq[j][k][0][1];
                                }
                                if(qwq[j][k][1][0]){
                                    if(j<n&&j+1-w<=la)dp[j+1][k][1][0]+=qwq[j][k][1][0];
                                    if(k<n&&k+1-j<=lb)dp[j][k+1][1][k+1-j==lb]+=qwq[j][k][1][0];
                                    if(w<n&&w+1-k<=lc)dp[j][k][1][0]+=qwq[j][k][1][0];
                                }
                                if(qwq[j][k][1][1]){
                                    if(j<n&&j+1-w<=la)dp[j+1][k][1][1]+=qwq[j][k][1][1];
                                    if(k<n&&k+1-j<=lb)dp[j][k+1][1][1]+=qwq[j][k][1][1];
                                    if(w<n&&w+1-k<=lc)dp[j][k][1][1]+=qwq[j][k][1][1];
                                }
                            }
                        }
                    }
                    ans+=dp[n][n][1][1];
                }
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}