#include <algorithm>
#include <assert.h>
#include <bitset>
#include <chrono>
#include <cstring>
#include <functional>
#include <iostream>
#include <istream>
#include <map>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define endl '\n'

using namespace std;

const int S = 4;

vector<int> comb(vector<int> &a, vector<int> &b)
{
    vector<int> r(S);

    for (int i = 0; i < S; ++i)
        r[i] = b[a[i]];

    return r;
}

vector<int> mcomb(vector<vector<int>> x)
{
    auto r = x[0];

    for (int i = 1; i < x.size(); ++i)
        r = comb(r, x[i]);

    return r;
}

void print(vector<int> &a)
{
    for (auto x : a)
        cout << x << " ";
    cout << endl;
}

vector<int> eye, r0, r1, r2;
int p0, p1, p2;

vector<vector<int>> all;
vector<vector<int>> mul;
vector<int> inverse;

int find(vector<int> &a)
{
    for (int i = 0; i < all.size(); ++i)
        if (all[i] == a)
            return i;

    return -1;
}

void init()
{
    vector<int> p(S);
    iota(p.begin(), p.end(), 0);

    eye = p;

    vector<vector<int>> A0, A1, A2;

    do
    {
        auto pp = comb(p, p);

        if (pp == eye)
            A2.push_back(p);

        if (comb(pp, p) == eye)
            A0.push_back(p);

        if (pp != eye && comb(pp, pp) == eye)
        {
            A1.push_back(p);
        }

        all.push_back(p);
    } while (next_permutation(p.begin(), p.end()));

    mul = vector<vector<int>>(all.size(), vector<int>(all.size()));
    inverse = vector<int>(all.size(), -1);

    for (int i = 0; i < all.size(); ++i)
        for (int j = 0; j < all.size(); ++j)
        {
            auto x = comb(all[i], all[j]);
            mul[i][j] = find(x);

            if (mul[i][j] == 0)
                inverse[i] = j;
        }

    // cout << A0.size() << " " << A1.size() << " " << A2.size() << endl;

    for (auto a0 : A0)
    {
        if (a0 == eye)
            continue;
        for (auto a1 : A1)
        {
            if (a1 == eye)
                continue;

            if (a0 == a1)
                continue;

            for (auto a2 : A2)
            {
                if (a2 == eye)
                    continue;

                if (a0 == a2)
                    continue;
                if (a1 == a2)
                    continue;

                if (comb(a0, a0) != comb(a1, a2))
                    continue;

                if (mcomb({a1, a1, a1}) != comb(a2, a0))
                {
                    continue;
                }

                if (mcomb({a0, a1, a2}) != eye)
                    continue;

                r0 = a0;
                r1 = a1;
                r2 = a2;

                p0 = find(r0);
                p1 = find(r1);
                p2 = find(r2);
                return;
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    init();

    vector<int> P = {p0, p1, p2};

    // for (auto x : inverse)
    //     cout << x << " ";
    // cout << endl;

    int sz = all.size();

    // print(r0);
    // print(r1);
    // print(r2);

    // cout << p0 << " " << p1 << " " << p2 << endl;

    // for (int i = 0; i < sz; ++i)
    // {
    //     for (int j = 0; j < sz; ++j)
    //     {
    //         cout << mul[i][j] << " ";
    //     }
    //     cout << endl;
    // }

    int t;
    cin >> t;

    while (t--)
    {
        int n, m;
        cin >> n >> m;
        string s;
        cin >> s;

        vector<int> freq(sz);
        vector<long long> total(sz);

        freq[0] = 1;

        int cur = 0;

        for (auto x : s)
        {
            int p = P[x - '0'];
            cur = mul[cur][p];

            for (int j = 0; j < sz; ++j)
            {
                int interval = mul[j][cur];
                total[interval] += freq[j];
            }

            freq[inverse[cur]]++;
        }

        while (m--)
        {
            string q;
            cin >> q;

            int y = 0;

            for (auto x : q)
            {
                int p = P[x - '0'];
                y = mul[y][p];
            }

            cout << total[y] << endl;
        }
    }

    return 0;
}