#include <bits/stdc++.h>

using namespace std;

const int N = 65;

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

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;
//        if (n != 60) {
//            puts("-1");
//            continue;
//        }
        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;
                if (r3 < 0) continue;
                memset(f[0], 0, sizeof(f[0]));
                f[0][0][0][(!l1) | ((!l2) << 1)] = 1;
                for (int k = 1; k <= n * 3; ++k) {
                    memset(f[k & 1], 0, sizeof(f[k & 1]));
                    for (int p = 0; p < k && p <= n; ++p) {
                        for (int q = 0; p + q <= k && q <= n && q - p <= r2; ++q) {
                            unsigned int *tg = f[(k & 1) ^ 1][p][q];
                            int r = k - 1 - p - q;
                            if (r < 0 || r > n || r - q > r3 || p - r > r1) continue;
                            if ((S[k] == '?' || S[k] == 'A') && p - r + 1 <= r1) {
                                unsigned int *tf = f[k & 1][p + 1][q];
                                if (p - r + 1 >= l1) tf[1] += tg[0] + tg[1], tf[3] += tg[2] + tg[3];
                                else tf[0] += tg[0], tf[1] += tg[1], tf[2] += tg[2], tf[3] += tg[3];
                            }
                            if ((S[k] == '?' || S[k] == 'B') && q - p + 1 <= r2) {
                                unsigned int *tf = f[k & 1][p][q + 1];
                                if (q - p + 1 >= l2) tf[2] += tg[0] + tg[2], tf[3] += tg[1] + tg[3];
                                else tf[0] += tg[0], tf[1] += tg[1], tf[2] += tg[2], tf[3] += tg[3];
                            }
                            if ((S[k] == '?' || S[k] == 'C') && r - q + 1 <= r3) {
                                unsigned int *tf = f[k & 1][p][q];
                                tf[0] += tg[0], tf[1] += tg[1], tf[2] += tg[2], tf[3] += tg[3];
                            }
                        }
                    }
                }
                res += f[n & 1][n][n][3];
            }
        }
        printf("%u\n", res);
    }
    return 0;
}