#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int px[N],py[N],fx[N],fy[N],ret[N];
vector<tuple<int,int,int,int,int>> ev[N];
struct UWU{
int ti,cnt=1;
vector<int> in,out,val;
vector<vector<int>> t;
void init(){
val.resize(N,0);
in.resize(N),out.resize(N);
ti=0;
t.resize(N,vector<int>(26,0));
}
void ins(string s,int id,int ty){
//if(ty==1) cout<<"ins" <<s <<"\n";
int now=1;
for(auto c:s){
if(t[now][c-'A']==0){
t[now][c-'A']=++cnt;
now=cnt;
}
else now=t[now][c-'A'];
//if(ty==1) cout<<now <<" ";
}
if(ty==0) px[id]=now;
else py[id]=now;
//cout<<"\n";
}
void dfs(int u,int p){
in[u]=++ti;
for(int i=0;i<26;i++){
int v=t[u][i];
if(v==p || v==0) continue;
dfs(v,u);
}
out[u]=ti;
}
int search(string x){
int now=1;
for(auto c:x){
if(t[now][c-'A']==0) return -1;
now=t[now][c-'A'];
}
return now;
}
}P,S;
struct QWQ{
vector<int> fw;
void init(){
fw.resize(N,0);
}
void upd(int i,int val){for(;i<N;i+=i&-i) fw[i]+=val;}
int qry(int i){int s=0; for(;i;i-=i&-i) s+=fw[i]; return s;}
}T;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,q; cin>>n >>q;
P.init(),S.init(),T.init();
for(int i=1;i<=n;i++){
string s; cin>>s;
P.ins(s,i,0);
reverse(s.begin(),s.end());
S.ins(s,i,1);
}
P.dfs(1,1);
S.dfs(1,1);
// for(int i=1;i<=S.cnt;i++){
// cout<<S.in[i] <<" " <<S.out[i] <<"\n";
// }
//return 0;
int mne=INT_MAX,mxe=INT_MIN;
for(int i=1;i<=n;i++){
fx[i]=P.in[px[i]];
fy[i]=S.in[py[i]];
mne=min(mne,fx[i]);
mxe=max(mxe,fx[i]);
ev[fx[i]].push_back({0,fy[i],0,0,0});
}
// for(int i=1;i<=n;i++) cout<<fx[i] <<" " <<fy[i] <<"\n";
// cout<<"\n";
//position in 2D plain is (fx[i],fy[i])
vector<tuple<int,int,int,int,int>> qr;
for(int i=0;i<q;i++){
string pre,suf; cin>>pre >>suf;
reverse(suf.begin(),suf.end());
int idp=P.search(pre),ids=S.search(suf);
if(idp==-1 || ids==-1){
//cout<<"un" <<idp <<" " <<ids <<"\n";
ret[i]=0;
continue;
}
//search in the (P.in[idp],P.out[idp]) X (S.in[ids],S.out[ids]) rectangle
ev[P.in[idp]-1].push_back({1,S.in[ids],S.out[ids],0,i});
mne=min(mne,P.in[idp]-1);
mxe=max(mxe,P.in[idp]-1);
ev[P.out[idp]].push_back({1,S.in[ids],S.out[ids],1,i});
mne=min(mne,P.out[idp]);
mxe=max(mxe,P.out[idp]);
//cout<<P.in[idp] <<" " <<P.out[idp] <<" " <<S.in[ids] <<" " <<S.out[ids] <<"\n";
}
for(int i=mne;i<=mxe;i++){
if(ev[i].empty()) continue;
//cout<<"vs" <<i <<"\n";
for(auto [type,x,y,use,id]:ev[i]){
//cout<<type <<" " <<x <<" " <<y <<" " <<use <<" " <<id <<"\n";
if(type==0){
T.upd(x,1);
}
else{
if(use==0) ret[id]-=T.qry(y)-T.qry(x-1);
else ret[id]+=T.qry(y)-T.qry(x-1);
}
}
}
for(int i=0;i<q;i++) cout<<ret[i] <<"\n";
}
