hambat @ 2023-08-03 21:29:25
#include<iostream>
#include<cstring>
using namespace std;
const int N=3e6+10;
int cnt[N],idx,n;
char str[N];
char son[N][75];
void add(char str[]){
int p=0;n=0;
for(int i=0;str[i];i++){
p=str[i]-'0';
if(!son[n][p])son[n][p]=++idx;
cnt[n]++;
n=son[n][p];
}
cnt[n]++;
}
int query(char str[]){
int p=0;n=0;
for(int i=0;str[i];i++){
p=str[i]-'0';
if(!son[n][p])return 0;
n=son[n][p];
}
return cnt[n];
}
int main(){
int T;
cin>>T;
while(T--){
int n,q;cin>>n>>q;
for(int i=0;i<n;i++){
cin>>str;
add(str);
}
for(int i=0;i<q;i++){
cin>>str;
int x=query(str);
printf("%d\n",x);
}
for(int i=1;i<=idx;i++)
for(int j=0;j<=74;j++)
son[i][j]=0;
for(int i=1;i<=idx;i++)
cnt[i]=0;
idx=0;
}
}