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