#include<bits/stdc++.h>
using namespace std;
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<=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){
              int a=0,b=0,c=0,ab=0,bc=0,ca=0,abc=i,bca=j,cab=n-i-j;
              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;
                }
              }
              f|=!a&&!b&&!c&&!ab&&!bc&&!ca&&!abc&&!bca&&!cab;
            }
      cout<<f<<'\n';
    }
  }
  return 0;
}