#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
// #define endl '\n'
typedef pair<int,int> PII;
typedef tree<pair<string,int>,null_type,less<pair<string,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int N=1e5+5;
int n,m;
ordered_set nums[N];
set<int>st;
int S[N];
int find(int x){
if(x!=S[x])S[x]=find(S[x]);
return S[x];
}
void merge(int u,int v){
u=find(u),v=find(v);
if(nums[u].size()<nums[v].size())swap(u,v);
for(auto x:nums[v]){
nums[u].insert(x);
}
S[v]=u;
nums[v].clear();
st.erase(v);
}
struct Query{
string s1,s2;
int id;
bool operator<(const Query a)const{
return s1.size()>a.s1.size();
}
};
void solve(){
cin>>n>>m;
string s[n];
for(int i=0;i<n;i++)cin>>s[i];
sort(s,s+n);
for(int i=0;i<n;i++){
st.insert(i);
S[i]=i;
string t=s[i];
reverse(t.begin(),t.end());
nums[i].insert({t,i});
}
Query Q[m];
for(int i=0;i<m;i++){
cin>>Q[i].s1>>Q[i].s2;
Q[i].id=i;
}
sort(Q,Q+m);
int ans[m];
for(int i=0;i<m;i++){
string s1=Q[i].s1,s2=Q[i].s2;
reverse(s2.begin(),s2.end());
int id=Q[i].id;
int l=0,r=n-1;
while(l<=r){
int mid=(l+r)>>1;
if(s[mid]>=s1)r=mid-1;
else l=mid+1;
}
int L=l;
r=n-1;
s1+='Z'+1;
while(l<=r){
int mid=(l+r)>>1;
if(s[mid]>s1)r=mid-1;
else l=mid+1;
}
int R=r;
if(L>R){
ans[id]=0;
continue;
}
auto it=st.lower_bound(L);
auto next=it;next++;
while(next!=st.end()&&*next<=R){
merge(*it,*next);
it=st.lower_bound(L);
next=it;next++;
}
int cnt1=nums[*it].order_of_key({s2,-1});
s2+='Z'+1;
int cnt2=nums[*it].order_of_key({s2,-1});
ans[id]=cnt2-cnt1;
}
for(int i=0;i<m;i++)cout<<ans[i]<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T=1;
// cin>>T;
for(int t=1;t<=T;t++){
solve();
}
}
