#include <bits/stdc++.h>

using namespace std;

const int N = 65;

unsigned int f[2][N][N][2][2];

signed main() {
    int T; scanf("%d%*d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        string S1, S2; cin >> S1 >> S2;
        vector<int> o1, o2;
        for (int i = 0; i <= n; ++i) {
            if (S1[i] == '1') o1.push_back(i);
            if (S2[i] == '1') o2.push_back(i);
        }
        string S; cin >> S, S = ' ' + S;
        unsigned int res = 0;
        for (int i = 0; i < (int)o1.size(); ++i) {
            for (int j = 0; j < (int)o2.size(); ++j) {
                int l1 = (!i ? 0 : o1[i - 1] + 1), r1 = o1[i],
                    l2 = (!j ? 0 : o2[j - 1] + 1), r2 = o2[j], r3 = n - r1 - r2;
                memset(f[0], 0, sizeof(f[0]));
                f[0][0][0][0 >= l1][0 >= l2] = 1;
                for (int k = 1; k <= n * 3; ++k) {
                    memset(f[k & 1], 0, sizeof(f[k & 1]));
                    for (int p = 0; p <= n; ++p) {
                        for (int q = 0; q <= n; ++q) {
                            int r = k - 1 - p - q;
                            if (r < 0 || r > n) continue;
                            for (int a = 0; a < 2; ++a) {
                                for (int b = 0; b < 2; ++b) {
                                    for (int c = 0; c < 3; ++c) {
                                        if ((S[k] != '?' && S[k] != "ABC"[c]) || !f[(k & 1) ^ 1][p][q][a][b]) continue;
                                        int tp = p + (c == 0), tq = q + (c == 1), tr = r + (c == 2);
                                        if (tp - tr <= r1 && tq - tp <= r2 && tr - tq <= r3) {
                                            f[k & 1][tp][tq][a || (tp - tr >= l1)][b || (tq - tp >= l2)] += f[(k & 1) ^ 1][p][q][a][b];
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
                res += f[n & 1][n][n][1][1];
            }
        }
        printf("%u\n", res);
    }
    return 0;
}