#include<bits/stdc++.h>
using namespace std;
inline bool pd(string t,int x,int y){
  int a=0,b=0,c=0,ab=0,bc=0,ca=0,abc=x,bca=y,cab=t.length()/3-x-y;
  for(char i:t){
    switch(i){
      case 'A':
        if(abc)abc--,bc++;
        else if(ab)ab--,b++;
        else if(a)a--;
        break;
      case 'B':
        if(bca)bca--,ca++;
        else if(bc)bc--,c++;
        else if(b)b--;
        break;
      case 'C':
        if(cab)cab--,ab++;
        else if(ca)ca--,a++;
        else if(c)c--;
        break;
    }
  }
  return !a&&!b&&!c&&!ab&&!bc&&!ca&&!abc&&!bca&&!cab;
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int t,id; cin>>t>>id;
  while(t--){
    int n; string s1,s2,t; cin>>n>>s1>>s2>>t;
    if(id==1||id==2){
      bool f=false;
      for(int i=0;i<=n;i++)
        if(s1[i]&1)
          for(int j=0;j<=n;j++)
            if(s2[j]&1)f|=pd(t,i,j);
      cout<<f<<'\n';
    }
    else if(n==6){
      string t2=t; int c=0;
      function<void(int)> dfs=[&](int u){
        if(u==n*3){
          bool f=false;
          for(int i=0;i<=n&&!f;i++)
            if(s1[i]&1)
              for(int j=0;j<=n&&!f;j++)
                if(s2[j]&1)f|=pd(t2,i,j);
          c+=f; return;
        }
        if(t[u]=='?')
          for(int i='A';i<'D';i++)
            t2[u]=i,dfs(u+1);
        else dfs(u+1);
      };
      dfs(0),cout<<c<<'\n';
    }
    else cout<<"-1\n";
  }
  return 0;
}