#include <bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize("O3,unroll-loops")
#define ii pair<int,int>
#define fir first
#define sec second
#define pb push_back
const int maxn=1e5;
struct trie{
trie *ch[26];
int mn,mx;
vector<int>isi;
trie(){
for(int q=0;q<26;q++){
ch[q]=0;
}
mn=1e18,mx=0;
}
void add(int idx,string s,int apa){
if(idx==s.length()){
mx=apa,mn=min(mn,apa);
return;
}
int nxt=s[idx]-'A';
if(!ch[nxt]){
ch[nxt]=new trie();
}
ch[nxt]->add(idx+1,s,apa);
mx=apa,mn=min(mn,apa);
}
void rev(int idx,string s,int apa){
if(idx==s.length()){
isi.pb(apa);
return;
}
int nxt=s[s.length()-idx-1]-'A';
if(!ch[nxt]){
ch[nxt]=new trie();
}
ch[nxt]->rev(idx+1,s,apa);
isi.pb(apa);
}
ii mnx(int idx,string s){
if(idx==s.length())return {mn,mx};
int apa=s[idx]-'A';
if(!ch[apa]){
return {1e18,0};
}
return ch[apa]->mnx(idx+1,s);
}
vector<int> src(int idx,string s){
if(idx==s.length())return isi;
int apa=s[idx]-'A';
if(!ch[apa]){
return {};
}
return ch[apa]->src(idx+1,s);
}
};
signed main(){
int n,qu;
cin>>n>>qu;
string s[n+1];
for(int q=1;q<=n;q++){
cin>>s[q];
}
sort(s+1,s+n+1);
trie cur;
for(int q=1;q<=n;q++){
cur.add(0,s[q],q);
cur.rev(0,s[q],q);
}
while(qu--){
string a,b;
cin>>a>>b;
ii apa=cur.mnx(0,a);
reverse(b.begin(),b.end());
vector<int>has=cur.src(0,b);
if(apa.fir==1e18 || apa.sec==0 || has.empty()){
cout<<0<<endl;
}
else{
int mul=lower_bound(has.begin(),has.end(),apa.fir)-has.begin();
int akh=upper_bound(has.begin(),has.end(),apa.sec)-has.begin();
cout<<akh-mul<<endl;
}
}
}
