#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6;
#pragma GCC optimize("O3,unroll-loops")
int cnt;
struct trie{
trie *ch[4]={NULL};
int in,out;
void upd(int i,string &s){
// cout<<i<<" "<<s<<endl;
if(i==s.length())return;
int cur=(s[i]-'A');
if(!ch[cur])ch[cur]=new trie();
ch[cur]->upd(i+1,s);
}
void euler(){
in=++cnt;
for(int q=0;q<4;q++){
if(ch[q])ch[q]->euler();
}
out=cnt;
}
pair<int,int> trav(int i,string &s){
if(i==s.length())return {in,out};
int cur=(s[i]-'A');
if(!ch[cur])return {-1,-1};
return ch[cur]->trav(i+1,s);
}
};
vector<array<int,3> >qu[maxn+2];
vector<int>pt[maxn+2];
struct seg{
int l,r;
int sum=0;
seg *lf,*rg;
void build(int x,int y){
l=x,r=y;
if(l==r)return;
int mid=(l+r)/2;
lf=new seg(); rg=new seg();
lf->build(l,mid); rg->build(mid+1,r);
}
void update(int pos){
if(l==r){
sum++; return;
}
int mid=(l+r)/2;
if(mid>=pos)lf->update(pos);
else rg->update(pos);
sum=lf->sum+rg->sum;
}
int query(int posl,int posr){
if(l>posr || r<posl)return 0;
if(l>=posl && r<=posr)return sum;
return lf->query(posl,posr)+rg->query(posl,posr);
}
};
vector<int>comp;
int ganti(int apa){
return lower_bound(comp.begin(),comp.end(),apa)-comp.begin();
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
trie pref,suf;
string s[n+1];
for(int q=1;q<=n;q++){
cin>>s[q];
for(int w=0;w<s[q].length();w++){
if(s[q][w]=='G')s[q][w]='B';
else if(s[q][w]=='U')s[q][w]='D';
}
pref.upd(0,s[q]);
reverse(s[q].begin(),s[q].end());
suf.upd(0,s[q]);
}
cnt=1;
pref.euler();
cnt=1; suf.euler();
for(int q=1;q<=n;q++){
pair<int,int>b=suf.trav(0,s[q]);
reverse(s[q].begin(),s[q].end());
pair<int,int>a=pref.trav(0,s[q]);
pt[a.first].push_back(b.first);
comp.push_back(b.first);
}
int ans[m+2];
for(int q=1;q<=m;q++){
ans[q]=0;
string x,y; cin>>x>>y;
for(int w=0;w<x.length();w++){
if(x[w]=='G')x[w]='B';
else if(x[w]=='U')x[w]='D';
}
for(int w=0;w<y.length();w++){
if(y[w]=='G')y[w]='B';
else if(y[w]=='U')y[w]='D';
}
pair<int,int>a=pref.trav(0,x);
reverse(y.begin(),y.end());
pair<int,int>b=suf.trav(0,y);
if(min(a.first,b.first)==-1){
continue;
}
qu[a.first-1].push_back({b.first,b.second,-q});
qu[a.second].push_back({b.first,b.second,q});
comp.push_back(b.first); comp.push_back(b.second);
}
sort(comp.begin(),comp.end());
comp.erase(unique(comp.begin(),comp.end()),comp.end());
seg slv; slv.build(0,comp.size());
for(int q=0;q<=maxn;q++){
for(auto x : pt[q]){
slv.update(ganti(x));
}
for(auto [c,d,id] : qu[q]){
c=ganti(c); d=ganti(d);
// cout<<c<<"K"<<d<<endl;
int brp=slv.query(c,d);
if(id<0)ans[abs(id)]-=brp;
else ans[id]+=brp;
}
}
for(int q=1;q<=m;q++){
cout<<ans[q]<<'\n';
}
}
