#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=2100050,inf=1e9;
void chmn(int &x,int y){x=min(x,y);}
void chmx(int &x,int y){x=max(x,y);}
int n,q;
string S[N];
void Sredi(string &s){
for(auto &i:s){
if(i=='C')i='B';
if(i=='G')i='C';
if(i=='U')i='D';
}
}
struct Trie{
int root,nc,numc,go[N][4];
vector<int>indexes[N];
Trie(){indm[0]=inf;indM[0]=-1;}
void Update(int &c,string &s,int i=0){
if(!c)c=++nc;
if(i>=s.size()){
indexes[c].pb(numc++);
return;
}
Update(go[c][s[i]-'A'],s,i+1);
}
int indm[N],indM[N];
vector<int>ind;
void DFS(int u){
indm[u]=inf;indM[u]=-1;
if(indexes[u].size()){
indm[u]=ind.size();
for(auto i:indexes[u])ind.pb(i);
indM[u]=(int)ind.size()-1;
}
for(int i=0;i<4;i++)if(go[u][i]){
DFS(go[u][i]);
chmn(indm[u],indm[go[u][i]]);
chmx(indM[u],indM[go[u][i]]);
}
}
int Get(int c,string &s,int i=0){
if(i>=s.size()) return c;
return Get(go[c][s[i]-'A'],s,i+1);
}
void Insert(string &s){Update(root,s);}
pair<int,int>Get(string &s){int u=Get(root,s);return {indm[u],indM[u]};}
}trie[2];
struct BIT{
int T[N+5];
void Update(int i,int x){i++;for(;i<=N;i+=i&-i)T[i]+=x;}
int Get(int i){i++;int x=0;for(;i>=1;i-=i&-i)x+=T[i];return x;}
int Get(int l,int r){return Get(r)-Get(l-1);}
}bt;
vector<array<int,4>>ev[N];
int main(){
scanf("%i%i",&n,&q);
for(int i=0;i<n;i++){
cin>>S[i];
Sredi(S[i]);
}
for(int i=0;i<n;i++){
trie[0].Insert(S[i]);
reverse(S[i].begin(),S[i].end());
trie[1].Insert(S[i]);
reverse(S[i].begin(),S[i].end());
}
trie[0].DFS(trie[0].root);
trie[1].DFS(trie[1].root);
int res[q+5]={0};
for(int I=0;I<q;I++){
string P,Q;cin>>P>>Q;
Sredi(P);Sredi(Q);
reverse(Q.begin(),Q.end());
auto [Lp,Rp]=trie[0].Get(P);
auto [Lq,Rq]=trie[1].Get(Q);
if(Lp<=Rp&&Lq<=Rq){
ev[Rp].pb({Lq,Rq,1,I});
if(Lp>0)ev[Lp-1].pb({Lq,Rq,-1,I});
}
}
vector<int>P=trie[0].ind,Q=trie[1].ind,invQ(n);
for(int i=0;i<n;i++)invQ[Q[i]]=i;
for(int i=0;i<n;i++){
bt.Update(invQ[P[i]],1);
for(auto [l,r,bit,I]:ev[i])res[I]+=bit*bt.Get(l,r);
}
for(int i=0;i<q;i++)printf("%i\n",res[i]);
return 0;
}
