#include<bits/stdc++.h>
#define ll int
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll>
using namespace :: std;
const ll mod=1e9+7;
const ll maxn=1e5+500;
const ll inf=1e9+900;
ll A[maxn];
ll ans[maxn];
vector<ll> seg[4*maxn];
ll l[maxn];
ll r[maxn];
ll ls[maxn];
ll rs[maxn];
void bild(ll l,ll r,ll node){
for(ll i=l;i<r;i++){
seg[node].pb(A[i]);
}
sort(seg[node].begin(),seg[node].end());
if(l+1==r)return;
ll mid=(l+r)/2;
bild(l,mid,2*node);
bild(mid,r,2*node+1);
}
ll find_ans(ll L,ll R,ll node,ll x){
if(ls[x]<=L && R<=rs[x]){
auto it=lower_bound(seg[node].begin(),seg[node].end(),l[x]);
auto itt=lower_bound(seg[node].begin(),seg[node].end(),r[x]);
return itt-it;
}
if(R<=ls[x] || rs[x]<=L){
return 0;
}
ll mid=(L+R)/2;
return find_ans(L,mid,2*node,x)+find_ans(mid,R,2*node+1,x);
}
string s[maxn];
pair<string,ll> ru[maxn];
string re[maxn];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n,q;
cin>>n>>q;
for(ll i=0;i<n;i++){
cin>>s[i];
}
sort(s,s+n);
for(ll i=0;i<n;i++){
ru[i]=mp(s[i],i);
reverse(ru[i].F.begin(),ru[i].F.end());
}
sort(ru,ru+n);
for(ll i=0;i<n;i++){
re[i]=ru[i].F;
A[i]=ru[i].S;
}
for(ll i=0;i<q;i++){
string a,b;
cin>>a>>b;
l[i]=lower_bound(s,s+n,a)-s;
a.back()++;
r[i]=lower_bound(s,s+n,a)-s;
reverse(b.begin(),b.end());
ls[i]=lower_bound(re,re+n,b)-re;
b.back()++;
rs[i]=lower_bound(re,re+n,b)-re;
}
bild(0,n,1);
for(ll i=0;i<q;i++){
ans[i]=find_ans(0,n,1,i);
}
for(ll i=0;i<q;i++){
cout<<ans[i]<<endl;
}
}
