#include <bits/stdc++.h>
using namespace std;
using perm = array<int, 4>;
const int N = 1e6 + 10;
int Case;
int n, m;

perm I, tr[3];

perm operator *(const perm &A, const perm &B) {
    perm r=I;
    for(int i = 0; i < 4; i += 1)
        r[i] = A[B[i]];
    return r;
}

char s[N];

int go[24][3];

int main() {
    for(int i = 0; i < 4; i += 1)
        I[i] = i;
    tr[0] = {1, 2, 0, 3};
    tr[1] = {3, 0, 1, 2};
    tr[2] = {3, 1, 2, 0};
    // auto E = tr[0] * tr[1] * tr[2];
    // for(int i = 0; i < 4; i += 1)
    //     cout << E[i] << " \n"[i + 1 == 4];
    map<perm, int> id;
    perm W = I;
    do {
        id[W] = id.size();
    }while(next_permutation(W.begin(), W.end()));
    for(auto [p, i]: id) {
        for(int j = 0; j < 3; j += 1)
            go[i][j] = id[p * tr[j]];
    }
    scanf("%d", &Case);
    while (Case--) {
        scanf("%d%d", &n, &m);
        scanf("%s", s + 1);
        array<long long, 24> sum, cnt;
        sum.fill(0);
        cnt.fill(0);
        cnt[0] += 1;
        for(int i = 1; i <= n; i += 1) {
            array<long long, 24> nc;
            nc.fill(0);
            for(int j = 0; j < 24; j += 1)
                nc[go[j][s[i] - '0']] += cnt[j];
            for(int j = 0; j < 24; j += 1)
                sum[j] += nc[j];
            nc[0] += 1;
            cnt.swap(nc);
        }
        while(m--) {
            scanf("%s", s + 1);
            int k = strlen(s + 1);
            perm w = I;
            for(int i = 1; i <= k; i += 1)
                w = w * tr[s[i] - '0'];
            printf("%lld\n", sum[id[w]]);
        }
    }
    return 0;
}