#include <bits/stdc++.h>
#define MAXN 65
using namespace std;
using uint = unsigned int;

int T, cid, n;
bool S1[MAXN], S2[MAXN];
string S;
uint dp[MAXN][MAXN][MAXN][2][2], ans;

void Add(uint &a, uint b) {a += b; return;}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> T >> cid;
	for (int tid = 1; tid <= T; ++tid) {
		cin >> n;
		for (int i = 0; i <= n; ++i) {
			char ch; cin >> ch;
			S1[i] = ch - '0';
		}
		for (int i = 0; i <= n; ++i) {
			char ch; cin >> ch;
			S2[i] = ch - '0';
		}
		cin >> S;
		if (n != 40) {cout << "-1\n"; continue;}
		ans = 0;
		for (int A = 0; A <= n; ++A) for (int B = 0; A + B <= n; ++B) {
			int C = n - A - B;
			int minabc = A, minbca = B;
			while (minabc <= n && !S1[minabc]) ++minabc;
			while (minbca <= n && !S1[minbca]) ++minbca;
			if (minabc + minbca > n) continue;
			C = min(C, n - minabc - minbca);
			memset(dp, 0, sizeof(dp));
			dp[0][0][0][A == 0][B == 0] = 1;
			for (int all = 0; all < n * 3; ++all) {
				for (int a = 0; a <= n && a <= all; ++a) for (int b = 0; b <= n && a + b <= all; ++b) {
					int c = all - a - b;
					for (int v1 : {0, 1}) for (int v2 : {0, 1}) {
						if (a < n && (S[all] == 'A' || S[all] == '?')) {
							int nowA = a - c + 1;
							if (nowA <= A) Add(dp[a + 1][b][c][v1 | (nowA == A)][v2], dp[a][b][c][v1][v2]);
						}
						if (b < n && (S[all] == 'B' || S[all] == '?')) {
							int nowB = b - a + 1;
							if (nowB <= B) Add(dp[a][b + 1][c][v1][v2 | (nowB == B)], dp[a][b][c][v1][v2]);
						}
						if (c < n && (S[all] == 'C' || S[all] == '?')) {
							int nowC = c - b + 1;
							if (nowC <= C) Add(dp[a][b][c + 1][v1][v2], dp[a][b][c][v1][v2]);
						}
					}
				}
			}
			Add(ans, dp[n][n][n][1][1]);
		}
		cout << ans << "\n";
	}
	return 0;
}