#include <bits/stdc++.h>

using namespace std;

const int N = 62;

int n;
char s0[N], s1[N];
char s[N * 3];
unsigned f[N][N][N][4];

inline void Work()
{
    scanf("%d%s%s%s", &n, s0, s1, s + 1);
    // if(n != 60) return void(puts("-1"));
    for(int i = 0; i <= n; i ++ ) s0[i] ^= 48, s1[i] ^= 48;
    unsigned ans = 0;
    for(int x = 0; x <= n; x ++ )
        for(int y = 0; y <= n - x; y ++ )
        {
            if(!s0[x] || !s1[y]) continue;
            int z = n - x - y;
            // printf("*%d %d %d\n", x, y, z);
            memset(f, 0, sizeof f);
            f[0][0][0][!x << 1 | !y] = 1;
            int p = x - 1, q = y - 1;
            while(p >= 0 && !s0[p]) p -- ;
            while(q >= 0 && !s1[q]) q -- ;
            for(int i = 0; i <= n; i ++ )
                for(int j = 0; j <= min(n, i + y); j ++ )
                    for(int k = max(!i & !j, i - x); k <= min(n, j + z); k ++ )
                    {
                        if(i && (s[i + j + k] == 'A' || s[i + j + k] == '?'))
                        {
                            f[i][j][k][0] += f[i - 1][j][k][0];
                            f[i][j][k][1] += f[i - 1][j][k][1];
                            f[i][j][k][2] += f[i - 1][j][k][2];
                            f[i][j][k][3] += f[i - 1][j][k][3];
                        }
                        if(j && (s[i + j + k] == 'B' || s[i + j + k] == '?'))
                        {
                            f[i][j][k][0] += f[i][j - 1][k][0];
                            f[i][j][k][1] += f[i][j - 1][k][1];
                            f[i][j][k][2] += f[i][j - 1][k][2];
                            f[i][j][k][3] += f[i][j - 1][k][3];
                        }
                        if(k && (s[i + j + k] == 'C' || s[i + j + k] == '?'))
                        {
                            f[i][j][k][0] += f[i][j][k - 1][0];
                            f[i][j][k][1] += f[i][j][k - 1][1];
                            f[i][j][k][2] += f[i][j][k - 1][2];
                            f[i][j][k][3] += f[i][j][k - 1][3];
                        }
                        if(i - k > p)
                        {
                            f[i][j][k][2] += f[i][j][k][0];
                            f[i][j][k][3] += f[i][j][k][1];
                            f[i][j][k][0] = f[i][j][k][1] = 0;
                        }
                        if(j - i > q)
                        {
                            f[i][j][k][1] += f[i][j][k][0];
                            f[i][j][k][3] += f[i][j][k][2];
                            f[i][j][k][0] = f[i][j][k][2] = 0;
                        }
                        // printf("!%d %d %d\n", i, j, k);
                    }
            ans += f[n][n][n][3];
        }
    printf("%u\n", ans);
}

int main()
{
    int T;
    scanf("%d%*d", &T);
    while(T -- ) Work();
    return 0;
}