#include <bits/stdc++.h>
#define uint unsigned
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

bool Mst;

const int maxn = 65;

int n, test;
uint f[maxn][maxn][maxn][2][2];
char s1[maxn], s2[maxn], s[maxn * 3];

void solve() {
	scanf("%d%s%s%s", &n, s1, s2, s + 1);
	if (n < 60) {
		puts("-1");
		return;
	}
	uint ans = 0;
	for (int A = 0; A <= n; ++A) {
		for (int B = 0; A + B <= n; ++B) {
			bool fl = 0;
			int mx = 0;
			for (int i = A; i <= n; ++i) {
				for (int j = B; i + j <= n; ++j) {
					if (s1[i] == '1' && s2[j] == '1') {
						fl = 1;
						mx = max(mx, n - i - j);
					}
				}
			}
			if (!fl) {
				continue;
			}
			int C = min(n - A - B, mx);
			mems(f, 0);
			f[0][0][0][A == 0][B == 0] = 1;
			for (int a = 0; a <= n; ++a) {
				for (int b = 0; b <= n; ++b) {
					if (b - a > B) {
						continue;
					}
					for (int c = 0; c <= n; ++c) {
						if (a - c > A || c - b > C) {
							continue;
						}
						if (a == n && b == n && c == n) {
							continue;
						}
						ull f00 = f[a][b][c][0][0], f01 = f[a][b][c][0][1], f10 = f[a][b][c][1][0], f11 = f[a][b][c][1][1];
						if ((s[a + b + c + 1] == 'A' || s[a + b + c + 1] == '?') && a + 1 - c <= A) {
							if (a + 1 - c == A) {
								f[a + 1][b][c][1][0] += f00 + f10;
								f[a + 1][b][c][1][1] += f01 + f11;
							} else {
								f[a + 1][b][c][0][0] += f00;
								f[a + 1][b][c][0][1] += f01;
								f[a + 1][b][c][1][0] += f10;
								f[a + 1][b][c][1][1] += f11;
							}
						}
						if ((s[a + b + c + 1] == 'B' || s[a + b + c + 1] == '?') && b + 1 - a <= B) {
							if (b + 1 - a == B) {
								f[a][b + 1][c][0][1] += f00 + f01;
								f[a][b + 1][c][1][1] += f10 + f11;
							} else {
								f[a][b + 1][c][0][0] += f00;
								f[a][b + 1][c][0][1] += f01;
								f[a][b + 1][c][1][0] += f10;
								f[a][b + 1][c][1][1] += f11;
							}
						}
						if ((s[a + b + c + 1] == 'C' || s[a + b + c + 1] == '?') && c + 1 - b <= C) {
							f[a][b][c + 1][0][0] += f00;
							f[a][b][c + 1][0][1] += f01;
							f[a][b][c + 1][1][0] += f10;
							f[a][b][c + 1][1][1] += f11;
						}
					}
				}
			}
			ans += f[n][n][n][1][1];
		}
	}
	printf("%u\n", ans);
}

bool Med;

int main() {
	fprintf(stderr, "%.2lf MB\n", (&Mst - &Med) / 1048576.);
	int T = 1;
	scanf("%d%d", &T, &test);
	while (T--) {
		solve();
	}
	return 0;
}