#include <bits/stdc++.h>

#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using u32 = unsigned int;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T>inline void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T>inline void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

const int maxn = 65;
const int maxm = 200;

int t, sid, n, a[maxm], nxta[maxn], nxtb[maxn];
string ca, cb, s;
u32 f[maxn][maxn][maxn][2][2];

void work() {
  cin >> n >> ca >> cb >> s;
  if (n != 60) return cout << "-1\n", void();
  nxta[n + 1] = nxtb[n + 1] = n + 1;
  per (i, n, 0) {
    nxta[i] = (ca[i] == '1' ? i : nxta[i + 1]);
    nxtb[i] = (cb[i] == '1' ? i : nxtb[i + 1]);
  }
  rep (i, 1, 3 * n) a[i] = (s[i - 1] == '?' ? -1 : s[i - 1] - 'A');
  u32 ans = 0;
  rep (A, 0, n) rep (B, 0, n - A) {
    if (nxta[A] > n || nxtb[B] > n) continue;
    int C = n - nxta[A] - nxtb[B];
    if (C < 0) continue;
    memset(f, 0, sizeof(f));
    f[0][0][0][A == 0][B == 0] = 1;
    // i - k <= A, j - i <= B, k - j <= C
    // j <= i + B, k <= j + C, k >= i - A
    rep (i, 0, n) rep (j, 0, min(n, i + B)) rep (k, max(0, i - A), min(n, j + C)) {
      if (i + j + k == 3 * n) continue;
      int val = a[i + j + k + 1], ta = (i + 1 - k == A), tb = (j + 1 - i == B);
      if ((val == -1 || val == 0) && i < n && i + 1 - k <= A) {
        f[i + 1][j][k][ta][0] += f[i][j][k][0][0];
        f[i + 1][j][k][ta][1] += f[i][j][k][0][1];
        f[i + 1][j][k][1][0] += f[i][j][k][1][0];
        f[i + 1][j][k][1][1] += f[i][j][k][1][1];
      }
      if ((val == -1 || val == 1) && j < n && j + 1 - i <= B) {
        f[i][j + 1][k][0][tb] += f[i][j][k][0][0];
        f[i][j + 1][k][0][1] += f[i][j][k][0][1];
        f[i][j + 1][k][1][tb] += f[i][j][k][1][0];
        f[i][j + 1][k][1][1] += f[i][j][k][1][1];
      }
      if ((val == -1 || val == 2) && k < n && k + 1 - j <= C) {
        f[i][j][k + 1][0][0] += f[i][j][k][0][0];
        f[i][j][k + 1][0][1] += f[i][j][k][0][1];
        f[i][j][k + 1][1][0] += f[i][j][k][1][0];
        f[i][j][k + 1][1][1] += f[i][j][k][1][1];
      }
    }
    ans += f[n][n][n][1][1];
  }
  cout << ans << '\n';
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  cin >> t >> sid;
  while (t--) work();
}