ShizukuQWQ @ 2023-02-21 10:41:36
#include<bits/stdc++.h>
using namespace std;
int p=1,t,n,m;
char s[3000005];
int aa(char x){
if(x>='A'&&x<='Z') return int(x-'A');
if(x>='a'&&x<='z') return int(x-'a'+26);
if(x>='0'&&x<='9') return int(x-'0'+52);
}
struct node{
int cnt,nx[65];
}tree[3000010];
void insert(){
p=0;
for(int i=0;i<strlen(s);i++){
int v=aa(s[i]);
if(!tree[p].nx[v]){
tree[p].nx[v]=++t;
}
p=tree[p].nx[v];
tree[p].cnt++;
}
}
int find(){
p=0;
for(int i=0;i<strlen(s);i++){
int v=aa(s[i]);
if(!tree[p].nx[v]){
cout<<0<<endl;
return 0;
}
p=tree[p].nx[v];
}
printf("%d\n",tree[p].cnt);
}
int main(){
int _;
cin>>_;
while(_--){
for(int i=0;i<=t;i++) for(int j=0;j<=64;j++) tree[i].nx[j]=0;
for(int i=0;i<=t;i++) tree[i].cnt=0;
t=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",s);
insert();
}
for(int i=1;i<=m;i++){
scanf("%s",s);
find();
}
}
}