#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)

vector<vector<int> >MULT;
const int sz=24;
string s[sz];
bool vis[sz];
int tab[sz][sz];
int inv[sz];
int A;
int B;
int C;
void DFS(int node){
	//cout<<node<<endl;
	vis[node]=true;
	if(!vis[MULT[0][node]]){
		s[MULT[0][node]]=s[node]+"0";
		DFS(MULT[0][node]);
	}
	if(!vis[MULT[1][node]]){
		s[MULT[1][node]]=s[node]+"2";
		DFS(MULT[1][node]);
	}
}
int Apply(string s, int x){
	trav(a,s){
		if(a=='0')x=MULT[0][x];
		else x=MULT[1][x];
	}
	return x;
}
vector<int> idx[sz];
int cnttab[sz][sz];
lld Count(vector<int> &A,vector<int> &B){
	
	int ptr=0;
	lld ans=0;
	
	rep(i,0,(int)B.size()){
		while(ptr<(int)A.size() && A[ptr]<B[i])ptr++;
		ans+=ptr;
	}
	return ans;
}
int calcval(string s){
	int cur=0;
	rep(i,0,(int)s.size()){
		if(s[i]=='0'){
			cur=tab[cur][A];
		}
		if(s[i]=='1'){
			cur=tab[cur][B];
		}
		if(s[i]=='2'){
			cur=tab[cur][C];
		}
	}
	return cur;
}
void solve(){
	rep(i,0,sz){
		idx[i].clear();
	}
	int n,m;
	cin>>n>>m;
	string S;
	cin>>S;
	vector<int> pref(n+1,0);
	int cur=0;
	rep(i,0,n){
		//cout<<s[i]<<" ";
		if(S[i]=='0'){
			cur=tab[cur][A];
		}
		if(S[i]=='1'){
			cur=tab[cur][B];
		}
		if(S[i]=='2'){
			cur=tab[cur][C];
		}
		pref[i+1]=cur;
	}
	rep(i,0,n+1){
		idx[pref[i]].push_back(i);
	}
	rep(i,0,sz){
		rep(j,0,sz){
			cnttab[i][j]=Count(idx[i],idx[j]);
		}
	}
	string t;
	while(m--){
		cin>>t;
		int v=calcval(t);
		lld ans=0;
		rep(i,0,sz){
			//cout<<i<<" "<<tab[i][v]<<" "<<cnttab[i][tab[i][v]]<<endl;
			ans+=cnttab[i][tab[i][v]];
		}
		cout<<ans<<"\n";
	}
}

int main(){
	rep(i,0,sz)vis[i]=0;
	MULT={{3, 2, 5, 4, 0, 1, 13, 12, 16, 17, 14, 15, 19, 18, 22, 23, 20, 21, 6, 7, 8, 9, 10, 11}, {6, 7, 8, 9, 10, 11, 0, 1, 2, 3, 4, 5, 14, 15, 12, 13, 17, 16, 20, 21, 18, 19, 23, 22}};
	DFS(0);
	rep(i,0,sz){
		rep(j,0,sz){
			tab[i][j]=Apply(s[j],i);
			if(tab[i][j]==1)inv[i]=j;
		}
	}
	A=MULT[0][0];
	C=MULT[1][0];
	B=Apply("001",0);
	//~ rep(i,0,sz)cout<<i<<" "<<s[i]<<endl;
	//~ cout<<endl;
	//~ cout<<A<<" "<<tab[0][A]<<endl;
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	cin>>tt;
	while(tt--){
		solve();
	}
}