#include<bits/stdc++.h>
#define S second
#define F first
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
int inf = 1e9;
const int maxn = 1e5+20;
vector<string> vec;
vector<string> tmp;
vector<string> seg[maxn*4];
string nxt(string s){
int n = s.size();
string t=s;
t[n-1]++;
return t;
}
void RVR(string&s){
int n = s.size();
for(int i=0,j=n-1;i < j;i++,j--){
swap(s[i],s[j]);
}
}
void build(int s,int e,int v){
if(e-s<2){
seg[v].push_back(tmp[s]);
return;
}
int mid = (s+e)/2;
build(s,mid,2*v);
build(mid,e,2*v+1);
int l=0,r=0;
while(l<seg[2*v].size() || r<seg[2*v+1].size()){
if(l>=seg[2*v].size() || (r<seg[2*v+1].size() && seg[2*v+1][r]<=seg[2*v][l])){
seg[v].push_back(seg[2*v+1][r]);
r++;
}else{
seg[v].push_back(seg[2*v][l]);
l++;
}
}
}
int ans(int s,int e,int v,int l,int r,string ll,string rr){
if(l<=s && e<=r){
return lower_bound(seg[v].begin(),seg[v].end(),rr)-lower_bound(seg[v].begin(),seg[v].end(),ll);
}
if(l>=e || s>=r){
return 0;
}
int mid = (s+e)/2;
return ans(s,mid,2*v,l,r,ll,rr)+ans(mid,e,2*v+1,l,r,ll,rr);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++){
string s;
cin>>s;
vec.push_back(s);
}
sort(vec.begin(),vec.end());
for(string s:vec){
RVR(s);
tmp.push_back(s);
}
int sz = tmp.size();
build(0,sz,1);
for(int i=0;i<m;i++){
string p,q;
cin>>p>>q;
int l = lower_bound(vec.begin(),vec.end(),p)-vec.begin();
int r = lower_bound(vec.begin(),vec.end(),nxt(p))-vec.begin();
RVR(q);
//cout<<l<<" "<<r<<"\n";
cout<<ans(0,sz,1,l,r,q,nxt(q))<<"\n";
}
return 0;
}
