#include<bits/stdc++.h>
#define uint unsigned int
using namespace std;
const int N=65;
int n; uint ans,dp[N][N][N];
char s1[N],s2[N],s[N*3];
uint calc(int a,int b,int c){
    if(a<0||b<0) return 0;
    memset(dp,0,sizeof(dp));
    dp[0][0][0]=1;
    for(int i=0;i<=n;++i){
        for(int j=0;j<=min(n,i+b);++j){
            for(int k=max(0,i-a);k<=min(n,j+c);++k){
                int now=7;
                if(i+j+k+1<=3*n&&s[i+j+k+1]!='?') now=1<<(int)(s[i+j+k+1]-'A');
                if((now&1)&&i<n) dp[i+1][j][k]+=dp[i][j][k];
                if((now&2)&&j<n) dp[i][j+1][k]+=dp[i][j][k];
                if((now&4)&&k<n) dp[i][j][k+1]+=dp[i][j][k];
            }
        }
    }
    return dp[n][n][n];
}
int main(){
    int _,id; scanf("%d%d",&_,&id);
    while(_--){
        scanf("%d%s%s%s",&n,s1,s2,s+1),ans=0;
        for(int a=0;a<=n;++a)
            for(int b=0;b<=n;++b){
                int a1=a,b1=b;
                for(;a1<=n&&s1[a1]=='0';++a1) ;
                for(;b1<=n&&s2[b1]=='0';++b1) ;
                int c=n-a1-b1;
                if(c>=0) ans+=calc(a,b,c)-calc(a-1,b,c)-calc(a,b-1,c)+calc(a-1,b-1,c);
            }
        printf("%u\n",ans);
    }


    return 0;
}