// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "\33[32m[" << __LINE__ << "]\33[m "
#define SZ(x) ((int) x.size() - 1)
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> T& chkmax(T& x, T y) {return x = max(x, y);}
template <typename T> T& chkmin(T& x, T y) {return x = min(x, y);}
template <typename T> T& read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = - f;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	return x *= f;
}
const int N = 65;
unsigned f[N][N][N][2][2];
string s1, s2, st;
signed main() {
	ios::sync_with_stdio(0); // don't use puts
	cin.tie(0), cout.tie(0);
	int T, id;
	cin >> T >> id;
	F(i, 1, T) {
		int n;
		cin >> n >> s1 >> s2 >> st;
		if (n == 60) {
			st = ' ' + st;
			unsigned ans = 0;
			F(i, 0, n) {
				F(j, 0, n - i) {
					int f1 = n + 1, f2 = n + 1;
					F(o, i, n)
						if (s1[o] == '1') {
							f1 = o;
							break;
						}
					F(o, j, n)
						if (s2[o] == '1') {
							f2 = o;
							break;
						}
					if (f1 + f2 > n) break;
					int f3 = n - f1 - f2;
					ms(f, 0);
					f[0][0][0][i == 0][j == 0] = 1;
					F(a, 0, n)
						F(b, 0, min(n, a + j))
							F(c, max(0, a - i), min(n, b + f3)) {
								int w = a + b + c + 1;
								if (w > 3 * n) continue;
								F(p, (a - c == i), 1)
									F(q, (b - a == j), 1) if (f[a][b][c][p][q]) {
										if (st[w] == '?' || st[w] == 'A') {
											if (a < n && a + 1 - c <= i) f[a + 1][b][c][p | (a + 1 - c == i)][q] += f[a][b][c][p][q];
										}
										if (st[w] == '?' || st[w] == 'B') {
											if (b < n && b + 1 - a <= j) f[a][b + 1][c][p][q | (b + 1 - a == j)] += f[a][b][c][p][q];
										}
										if (st[w] == '?' || st[w] == 'C') {
											if (c < n && c + 1 - b <= f3) f[a][b][c + 1][p][q] += f[a][b][c][p][q];
										}
									}
							}
					// debug << i << " " << j << " " << f1 << ' ' << f2 << ' ' << f3 << ' ' << f[n][n][n][1][1] << '\n';
					ans += f[n][n][n][1][1];
				}
			}
			cout << ans << '\n';
		} else cout << - 1 << '\n';
	}
	return 0;
}
/* why?
*/