#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 != 60) {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 && !S2[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 a = 0; a <= n; ++a) for (int b = 0; b <= n; ++b) for (int c = 0; c <= n; ++c) {
				int all = a + b + c;
				for (bool v1 : {0, 1}) for (bool 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;
}