#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
#define gg exit(0);
const int N=100010;
int n,m;
int ans[N];
string s[N],pf[N],sf[N];
vector<int> st[N],ed[N];
int it=1;
int mx[2000010],mn[2000010],sz[2000010];
int nxt[2000010][5];
int mode;
void norm(string &s){
forv(i,s) i=i=='U'?'B':i=='G'?'D':i;
}
void add(int t){
int i=1;
forv(j,s[t]){
if(!nxt[i][j-'A']) nxt[i][j-'A']=++it;
mx[i]=t; mn[i]=mn[i]?mn[i]:t; if(mode) sz[i]++;
i=nxt[i][j-'A'];
}
mx[i]=t; mn[i]=mn[i]?mn[i]:t; if(mode) sz[i]++;
}
ii que(const string&s){
int i=1;
forv(j,s){
if(!nxt[i][j-'A']) return {0,0};
i=nxt[i][j-'A'];
}
return {mode?sz[i]:mn[i],mx[i]};
}
main(){
#define task "RNA"
//freopen(task".inp","r",stdin);
//freopen(task".out","w",stdout);
fasty;
cin>>n>>m;
forinc(i,1,n){
cin>>s[i];
norm(s[i]);
}
sort(s+1,s+n+1);
forinc(i,1,n) add(i);
forinc(i,1,m){
cin>>pf[i]>>sf[i];
norm(pf[i]), norm(sf[i]);
reverse(all(sf[i]));
ii j=que(pf[i]);
if(j.fi) st[j.fi-1].pb(i);
ed[j.se].pb(i);
}
reset(mx,0);
reset(mn,0);
reset(nxt,0);
mode=1;
forinc(i,1,n){
reverse(all(s[i]));
add(i);
forv(j,st[i]) ans[j]-=que(sf[j]).fi;
forv(j,ed[i]) ans[j]+=que(sf[j]).fi;
}
forinc(i,1,m){
cout<<ans[i]<<"\n";
}
}
