#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define rit string::reverse_iterator
ll n,m;
struct tri
{
map<char,tri*>ch;
vector<ll>ind;
void insert(rit st,rit dr,ll poz)
{
ind.push_back(poz);
if (st==dr)
return ;
char cha=*st;
if (ch.find(cha)==ch.end())
ch[cha]=new tri();
ch[cha]->insert(next(st),dr,poz);
}
ll cnt(rit st,rit dr,ll l,ll r)
{
if (st==dr)
return lower_bound(ind.begin(),ind.end(),r)-lower_bound(ind.begin(),ind.end(),l);
char cha=*st;
if (ch.find(cha)==ch.end())
return 0;
return ch[cha]->cnt(next(st),dr,l,r);
}
}trie;
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
scanf("%lld%lld\n",&n,&m);
vector<string>s(n);
ll i;
for(i=0;i<n;i++)
cin>>s[i];
sort(s.begin(),s.end());
for(i=0;i<n;i++)
trie.insert(s[i].rbegin(),s[i].rend(),i);
while(m--){
string x,y;
cin>>x>>y;
ll st=lower_bound(s.begin(),s.end(),x)-s.begin();
++x.back();
ll dr=lower_bound(s.begin(),s.end(),x)-s.begin();
printf("%lld\n",trie.cnt(y.rbegin(),y.rend(),st,dr));
}
return 0;
}
