//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
vector<string> vec;
unordered_map<string,int> Mp;
vector<int> fa;
vector<int> state;
vector<vector<int>> trans;
vector<int> inverse;
vector<string> id;
void init()
{
	const int len=12,lim=4;
	vec.pb("");
	for(int i=1;i<=len;i++)
	{
		int n=sz(vec);
		for(int j=0;j<n;j++)
			if(sz(vec[j])==i-1)
				for(int k=0;k<3;k++)
					vec.pb(vec[j]+(char)(k^48));
	}
	for(int i=0;i<sz(vec);i++)
		Mp[vec[i]]=i;
	fa.resize(sz(vec));
	for(int i=0;i<sz(fa);i++)
		fa[i]=i;
	auto connect=[&](int u,int v)
	{
		while(fa[u]!=u)
			u=fa[u]=fa[fa[u]];
		while(fa[v]!=v)
			v=fa[v]=fa[fa[v]];
		if(u>v) swap(u,v);
		fa[v]=u;
	};
	for(int i=0;i<sz(vec);i++)
	{
		string cur=vec[i];
		for(int j=0;j<sz(cur)-2;j++)
			if(cur.substr(j,3)=="111")
			{
				string ns=cur.substr(0,j)+"20"+cur.substr(j+3);
				connect(i,Mp[ns]);
			}
		for(int j=0;j<sz(cur)-2;j++)
			if(cur.substr(j,3)=="012")
			{
				string ns=cur.substr(0,j)+cur.substr(j+3);
				connect(i,Mp[ns]);
			}
		for(int j=0;j<sz(cur)-1;j++)
			if(cur.substr(j,2)=="00")
			{
				string ns=cur.substr(0,j)+"12"+cur.substr(j+2);
				connect(i,Mp[ns]);
			}
		for(int j=0;j<sz(cur)-1;j++)
			if(cur.substr(j,2)=="22")
			{
				string ns=cur.substr(0,j)+cur.substr(j+2);
				connect(i,Mp[ns]);
			}
	}
	state.resize(sz(vec));
	int tot=0;
	for(int i=0;i<sz(vec);i++)
		if(fa[i]==i&&sz(vec[i])<=lim)
			state[i]=tot++;
	id.resize(tot);
	for(int i=0;i<sz(vec);i++)
		if(fa[i]==i&&sz(vec[i])<=lim)
			id[state[i]]=vec[i];
	for(int i=0;i<sz(vec);i++)
	{
		int tmp=i;
		while(fa[tmp]!=tmp) tmp=fa[tmp]=fa[fa[tmp]];
		state[i]=state[tmp];
	}
	inverse.resize(tot);
	trans.resize(tot);
	for(int i=0;i<tot;i++)
	{
		trans[i].resize(tot);
		for(int j=0;j<tot;j++)
			trans[i][j]=state[Mp[id[i]+id[j]]];
	}
	for(int i=0;i<tot;i++)
		for(int j=0;j<tot;j++)
			if(!trans[i][j])
				inverse[i]=j;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	init();
	int t;
	cin>>t;
	while(t--)
	{
		int n,m;
		cin>>n>>m;
		vector<ll> cnt(sz(id));
		vector<ll> ans(sz(id));
		string s;
		cin>>s;
		int cur=0;
		cnt[0]++;
		for(int i=sz(s)-1;i>=0;i--)
		{
			cur=trans[state[Mp[s.substr(i,1)]]][cur];
			for(int j=0;j<sz(cnt);j++)
				ans[trans[cur][j]]+=cnt[j];
			cnt[inverse[cur]]++;
		}
		while(m--)
		{
			string t;
			cin>>t;
			int st=0;
			for(int i=0;i<sz(t);i++)
				st=trans[st][state[Mp[t.substr(i,1)]]];
			cout<<ans[st]<<'\n';
		}
	}
	return 0;
}