#include <bits/stdc++.h>
#define int long long
#define F first
#define S second
#define pb push_back
#define pii pair <int,int>
#define all(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
using namespace std;
const int N=2e6+9,LG=22;
int nxt[2][N][4],cnt[2],ttt=0;
string s[N];
int id[2][N],st[2][N],ft[2][N];
pii arr[N];
int seg[LG][2*N];
int ADD(string t,int tt){
int cur=0;
for(int i=0;i<SZ(t);i++){
if(nxt[tt][cur][t[i]-'A']){
cur=nxt[tt][cur][t[i]-'A'];
}
else{
nxt[tt][cur][t[i]-'A']=cnt[tt]++;
cur=nxt[tt][cur][t[i]-'A'];
}
}
return cur;
}
void DFS(int u,int tt){
st[tt][u]=ttt++;
for(int i=0;i<4;i++) if(nxt[tt][u][i]) DFS(nxt[tt][u][i],tt);
ft[tt][u]=ttt;
}
int GO(string t,int tt){
int cur=0;
for(int i=0;i<SZ(t);i++){
if(!nxt[tt][cur][t[i]-'A']) return -1;
cur=nxt[tt][cur][t[i]-'A'];
}
return cur;
}
void BUILD(int l,int r,int h){
if(l==r){
seg[h][l]=arr[l].S;
return ;
}
int mid=(l+r)/2;
BUILD(l,mid,h+1);
BUILD(mid+1,r,h+1);
int ll=l,rr=mid+1,pos=l;
while(ll<=mid && rr<=r){
if(seg[h+1][ll]<seg[h+1][rr]){
seg[h][pos]=seg[h+1][ll];
ll++; pos++;
}
else{
seg[h][pos]=seg[h+1][rr];
pos++; rr++;
}
}
while(ll<=mid) seg[h][pos++]=seg[h+1][ll++];
while(rr<=r) seg[h][pos++]=seg[h+1][rr++];
}
int GET(int l,int r,int h,int ql,int qr,int mn,int mx){
if(arr[l].F>qr || arr[r].F<ql) return 0;
if(arr[l].F>=ql && arr[r].F<=qr){
int num=lower_bound(seg[h]+l,seg[h]+r+1,mx)-lower_bound(seg[h]+l,seg[h]+r+1,mn);
return num;
}
int mid=(l+r)/2;
return GET(l,mid,h+1,ql,qr,mn,mx)+GET(mid+1,r,h+1,ql,qr,mn,mx);
}
int32_t main(){
ios::sync_with_stdio(0);cin.tie(0);
int n,q;
cin>>n>>q;
cnt[0]=cnt[1]=1;
for(int i=0;i<n;i++){
cin>>s[i];
for(int j=0;j<SZ(s[i]);j++){
if(s[i][j]=='G') s[i][j]='B';
if(s[i][j]=='U') s[i][j]='D';
}
id[0][i]=ADD(s[i],0);
reverse(all(s[i]));
id[1][i]=ADD(s[i],1);
// cout<<id[0][i]<<" "<<id[1][i]<<endl;
}
DFS(0,0);
ttt=0;
DFS(0,1);
for(int i=0;i<n;i++){
arr[i]={st[0][id[0][i]],st[1][id[1][i]]};
// cout<<arr[i].F<<" "<<arr[i].S<<endl;
}
sort(arr,arr+n);
BUILD(0,n-1,0);
while(q--){
string s1,s2;
cin>>s1>>s2;
reverse(all(s2));
for(int j=0;j<SZ(s1);j++){
if(s1[j]=='G') s1[j]='B';
if(s1[j]=='U') s1[j]='D';
}
for(int j=0;j<SZ(s2);j++){
if(s2[j]=='G') s2[j]='B';
if(s2[j]=='U') s2[j]='D';
}
int id1=GO(s1,0),id2=GO(s2,1);
if(id1==-1 || id2==-1){
cout<<0<<'\n';
continue ;
}
cout<<GET(0,n-1,0,st[0][id1],ft[0][id1]-1,st[1][id2],ft[1][id2])<<'\n';
}
return 0;
}
