#include <bits/stdc++.h>
using namespace std;
int const MAX=2e6+5;
int Tpref[MAX][4];
int Tsuf[MAX][4];
int l[MAX],r[MAX];
vector<int>ind[MAX];
int n,m;
vector<string>v;
int trans[300];
int total_p,total_s;
void minself(int& x,int val){
if(x>val)
x=val;
}
void maxself(int& x,int val){
if(x<val)
x=val;
}
void add(int T[][4],string sir,int id,int nod,int type,int orig_id,int& total_id){
if(type==1){
minself(l[nod],orig_id);
maxself(r[nod],orig_id);
}
else
ind[nod].push_back(orig_id);
if(id<(int)sir.size()){
int& nou=T[nod][trans[sir[id]]];
if(nou==0){
nou=++total_id;
if(type==1){
l[nou]=n+1;
r[nou]=0;
}
}
add(T,sir,id+1,nou,type,orig_id,total_id);
}
}
void read(){
cin>>n>>m;
int i;
for(i=1;i<=n;++i){
string s;
cin>>s;
v.push_back(s);
}
l[0]=n+1;
r[0]=0;
sort(v.begin(),v.end());
trans['A']=0;
trans['C']=1;
trans['G']=2;
trans['U']=3;
for(i=0;i<n;++i){
add(Tpref,v[i],0,0,1,i+1,total_p);
reverse(v[i].begin(),v[i].end());
add(Tsuf,v[i],0,0,2,i+1,total_s);
}
}
int get_node(int T[][4],string sir,int id,int nod){
if(id==(int)sir.size())
return nod;
int& nou=T[nod][trans[sir[id]]];
if(nou)
return get_node(T,sir,id+1,nou);
return 0;
}
void process_queries(){
int i;
for(i=1;i<=m;++i){
string pref,suf;
cin>>pref>>suf;
int nodP=get_node(Tpref,pref,0,0);
reverse(suf.begin(),suf.end());
int nodS=get_node(Tsuf,suf,0,0);
if(nodP && nodS)
cout<<upper_bound(ind[nodS].begin(),ind[nodS].end(),r[nodP])-lower_bound(ind[nodS].begin(),ind[nodS].end(),l[nodP])<<'\n';
else
cout<<0<<'\n';
}
}
int main()
{
read();
process_queries();
return 0;
}
