#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=1e6+500;
const ll inf=1e9+900;
string s[maxn];
pair<string,ll> ru[maxn];
string re[maxn];
ll A[maxn];
ll l[maxn];
ll r[maxn];
ll ls[maxn];
ll rs[maxn];
ll ans[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;
// cout<<l[i]<<' '<<r[i]<<endl;
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;
}
for(ll i=0;i<q;i++){
for(ll j=ls[i];j<rs[i];j++){
if(l[i]<=A[j] && A[j]<r[i]){
ans[i]++;
}
}
}
for(ll i=0;i<q;i++){
cout<<ans[i]<<endl;
}
}
