#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#pragma GCC target("avx2")

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


namespace exper {
constexpr int N = 5;
int id(int x, int y) {
  return x * (N + 1) + y;
}
map<string, Int> cache;
Int solve(const string &s) {
  auto it = cache.find(s);
  if (it != cache.end()) return it->second;
  Int ret = 0;
  
  assert((int)s.size() % 3 == 0);
  const int n = s.size() / 3;
  if (n == 0) {
    ret |= 1LL << id(0, 0);
  } else {
    for (int i = 1; i < 3*n; ++i) if ((s[i] - s[0] - 1) % 3 == 0) {
      for (int j = i + 1; j < 3*n; ++j) if ((s[j] - s[i] - 1) % 3 == 0) {
        const Int res = solve(s.substr(1, i - 1) + s.substr(i + 1, j - (i + 1)) + s.substr(j + 1));
        ret |= res << ((s[0] == 'A') ? (N + 1) : (s[0] == 'B') ? 1 : 0);
      }
    }
  }
  
  return ret;
}
void run() {
  for (int n = 1; n <= N; ++n) {
    string s = string(n, 'A') + string(n, 'B') + string(n, 'C');
    do {
      const Int res = solve(s);
      int now[3] = {}, mxs[3] = {};
      for (int i = 0; i < 3*n; ++i) {
        ++now[s[i] - 'A'];
        chmax(mxs[0], now[0] - now[2]);
        chmax(mxs[1], now[1] - now[0]);
        chmax(mxs[2], now[2] - now[1]);
      }
      if (res) {
        printf("%s %d %d %d\n", s.c_str(), mxs[0], mxs[1], mxs[2]);
        for (int x = 0; x <= n; ++x) {
          for (int y = 0; x + y <= n; ++y) putchar(".#"[res >> id(x, y) & 1]);
          puts("");
        }
        assert(mxs[0] + mxs[1] + mxs[2] <= n);
        for (int x = 0; x <= n; ++x) for (int y = 0; x + y <= n; ++y) {
          const int z = n - x - y;
          assert((bool)(res >> id(x, y) & 1) == (x >= mxs[0] && y >= mxs[1] && z >= mxs[2]));
        }
      } else {
        assert(mxs[0] + mxs[1] + mxs[2] > n);
      }
    } while (next_permutation(s.begin(), s.end()));
    fflush(stdout);
    cerr << "DONE n = " << n << endl;
  }
}
}  // exper


constexpr unsigned ALL[61] = {1
,3
,48
,1077
,25950
,631596
,15361200
,373543344
,513491674
,3715046604
,2905885740
,1568880512
,2580218992
,1190440544
,717460800
,3773052672
,4125163354
,1253250684
,451796724
,588301280
,3790101036
,1976168152
,2307984512
,3414639104
,4155978864
,3748854816
,300437408
,2740636160
,342373696
,3437770880
,3706226944
,2582641664
,818675546
,4282719452
,4003661124
,2620370720
,3557104884
,1127743016
,1645938208
,544025216
,3328387628
,3785150760
,819081384
,2964923392
,755846272
,2114968832
,3614678528
,560097280
,3053794416
,804406688
,1928254944
,3311421696
,2927919008
,179566400
,4157937152
,2641385472
,2225157440
,2881464704
,3321196416
,2878195712
,2103642368
};

constexpr int MAX_N = 35;
constexpr int MAX_U = (MAX_N + 1) * (MAX_N + 2) * (MAX_N + 3) / 6;

int subtaskId;
int N;
char A[210], B[210], S[210];

int U;
int ids[MAX_N + 1][MAX_N + 1][MAX_N + 1];
int xs[MAX_U], ys[MAX_U], zs[MAX_U];
unsigned dp[2][MAX_N + 1][MAX_N + 1][MAX_U + 1];

int main() {
  // exper::run();
  
  for (int numCases; ~scanf("%d%d", &numCases, &subtaskId); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    scanf("%d", &N);
    scanf("%s", A);
    scanf("%s", B);
    scanf("%s", S);
    
    const int hatena = count(S, S + 3*N, '?');
    if (hatena == 0) {
      int now[3] = {};
      int x = 0, y = 0, z = 0;
      for (int i = 0; i < 3*N; ++i) {
        ++now[S[i] - 'A'];
        chmax(x, now[0] - now[2]);
        chmax(y, now[1] - now[0]);
        chmax(z, now[2] - now[1]);
      }
      const int d = N - (x + y + z);
      bool ok = false;
      for (int dx = 0; dx <= d; ++dx) for (int dy = 0; dx + dy <= d; ++dy) {
        ok = ok || (A[x + dx] == '1' && B[y + dy] == '1');
      }
      ok = ok && (now[0] == N && now[1] == N && now[2] == N);
      puts(ok ? "1" : "0");
    } else if (subtaskId == 3) {
      printf("%u\n", ALL[N]);
    } else if (N <= MAX_N) {
      U = 0;
      for (int x = 0; x <= N; ++x) for (int y = 0; x + y <= N; ++y) for (int z = 0; x + y + z <= N; ++z) {
        const int u = ids[x][y][z] = U++;
        xs[u] = x;
        ys[u] = y;
        zs[u] = z;
      }
      assert(U <= MAX_U);
      for (int x = 0; x <= N; ++x) for (int y = 0; y <= N; ++y) for (int z = 0; z <= N; ++z) if (x + y + z > N) ids[x][y][z] = U;
      for (int a = 0; a <= N; ++a) for (int b = 0; b <= N; ++b) memset(dp[0][a][b], 0, (U + 1) * sizeof(unsigned));
      dp[0][0][0][ids[0][0][0]] = 1;
      for (int i = 0; i < 3*N; ++i) {
        auto crt = dp[i & 1], nxt = dp[(i + 1) & 1];
        for (int a = 0; a <= N; ++a) for (int b = 0; b <= N; ++b) memset(nxt[a][b], 0, (U + 1) * sizeof(unsigned));
        for (int a = 0; a <= N; ++a) for (int b = 0; b <= N; ++b) {
          const int c = i - a - b;
          if (c >= 0) {
            const int x0 = max(a - c, 0);
            const int y0 = max(b - a, 0);
            const int z0 = max(c - b, 0);
            for (int x = x0; x + y0 + z0 <= N; ++x) for (int y = y0; x + y + z0 <= N; ++y) for (int z = z0; x + y + z <= N; ++z) {
              const int u = ids[x][y][z];
              if (crt[a][b][u]) {
                if (a < N && (S[i] == '?' || S[i] == 'A')) nxt[a + 1][b][(x == a-c) ? ids[a-c+1][y][z] : u] += crt[a][b][u];
                if (b < N && (S[i] == '?' || S[i] == 'B')) nxt[a][b + 1][(y == b-a) ? ids[x][b-a+1][z] : u] += crt[a][b][u];
                if (c < N && (S[i] == '?' || S[i] == 'C')) nxt[a][b]    [(z == c-b) ? ids[x][y][c-b+1] : u] += crt[a][b][u];
              }
            }
          }
        }
      }
      unsigned ans = 0;
      for (int x = 0; x <= N; ++x) for (int y = 0; x + y <= N; ++y) for (int z = 0; x + y + z <= N; ++z) {
        const int d = N - (x + y + z);
        bool ok = false;
        for (int dx = 0; dx <= d; ++dx) for (int dy = 0; dx + dy <= d; ++dy) {
          ok = ok || (A[x + dx] == '1' && B[y + dy] == '1');
        }
        if (ok) {
// cerr<<"ok "<<x<<" "<<y<<" "<<z<<": "<<dp[(3*N) & 1][N][N][ids[x][y][z]]<<endl;
          ans += dp[(3*N) & 1][N][N][ids[x][y][z]];
        }
      }
      printf("%u\n", ans);
    } else {
      puts("-1");
    }
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}