#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][2][2];

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;
            memset(f, 0, sizeof f);
            f[0][0][0][!x][!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 <= n; j ++ )
                    for(int k = 0; k <= n; k ++ )
                    {
                        auto Get=[&](int r, int s, int t)
                        {
                            if(r - t > x || s - r > y || t - s > z) return ;
                            f[r][s][t][r - t > p][s - r > q] += f[i][j][k][0][0];
                            f[r][s][t][r - t > p][    1    ] += f[i][j][k][0][1];
                            f[r][s][t][    1    ][s - r > q] += f[i][j][k][1][0];
                            f[r][s][t][    1    ][    1    ] += f[i][j][k][1][1];
                        };
                        if(s[i + j + k + 1] == 'A' || s[i + j + k + 1] == '?') Get(i + 1, j, k);
                        if(s[i + j + k + 1] == 'B' || s[i + j + k + 1] == '?') Get(i, j + 1, k);
                        if(s[i + j + k + 1] == 'C' || s[i + j + k + 1] == '?') Get(i, j, k + 1);
                    }
            ans += f[n][n][n][1][1];
        }
    printf("%u\n", ans);
}

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