#include <bits/stdc++.h>
#define MAXN 185
using namespace std;

int T, cid, n, ans;
int cA, cB, cC, cAB, cBC, cCA, cABC, cBCA, cCAB;
bool S1[MAXN], S2[MAXN], flag;
string S;

void dfs2(const int p) {
	if (max(max(cA, cB), cC) > (n - p + 1) / 2) return;
	if (p >= 3 * n) {
		if (cABC + cBCA + cCAB < n) return;
		if (!S1[cABC] || !S2[cBCA]) return;
		flag = 1;
		return;
	}
	if (S[p] == 'A') {
		if (cBC) {
			--cBC, ++cBCA;
			dfs2(p + 1);
			++cBC, --cBCA;
		}
		if (cC) {
			--cC, ++cCA;
			dfs2(p + 1);
			++cC, --cCA;
		}
		++cA;
		dfs2(p + 1);
		--cA;
	}
	else if (S[p] == 'B') {
		if (cCA) {
			--cCA, ++cCAB;
			dfs2(p + 1);
			++cCA, --cCAB;
		}
		if (cA) {
			--cA, ++cAB;
			dfs2(p + 1);
			++cA, --cAB;
		}
		++cB;
		dfs2(p + 1);
		--cB;
	}
	else {
		if (cAB) {
			--cAB, ++cABC;
			dfs2(p + 1);
			++cAB, --cABC;
		}
		if (cB) {
			--cB, ++cBC;
			dfs2(p + 1);
			++cB, --cBC;
		}
		++cC;
		dfs2(p + 1);
		--cC;
	}
	return;
}

void dfs1(const int p) {
	if (p >= 3 * n) {
		int cA = 0, cB = 0, cC = 0;
		for (int i = 0; i < 3 * n; ++i) {
			if (S[i] == 'A') ++cA;
			else if (S[i] == 'B') ++cB;
			else ++cC;
		}
		if (cA != n || cB != n || cC != n) return;
		flag = 0;
		dfs2(0);
		if (flag) ++ans;
		return;
	}
	if (S[p] != '?') dfs1(p + 1);
	else {
		S[p] = 'A', dfs1(p + 1);
		S[p] = 'B', dfs1(p + 1);
		S[p] = 'C', dfs1(p + 1);
		S[p] = '?';
	}
	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 ((cid <= 2 && n != 9) || (cid > 2 && n != 4)) {cout << "-1\n"; continue;}
		ans = 0, dfs1(0);
		cout << ans << "\n";
	}
	return 0;
}