#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define lb long double
#define flip(i) ((i)%2)^1
#define el "\n"
#define fre(name) freopen(name".INP","r",stdin); freopen(name".OUT","w",stdout)
using namespace std;
const int N=1e5+5;
const int M=2e6+5;
string s[N];
int n,m;
int curtrieid;
string a,b;
struct NODE
{
int child[26];
int mx=0,mn=0;
NODE()
{
for(int i=0;i<26;i++)
child[i]=-1;
}
}node[M];
vector<int>reverse_end[M];
void add(string &x,int id)
{
int p=0;
for(auto z : x)
{
if(node[p].child[z-'A']==-1) node[p].child[z-'A']=++curtrieid;
//cout<<p<<" "<<node[p].child[z-'A']<<" "<<z<<el;
p=node[p].child[z-'A'];
node[p].mx=id;
if(!node[p].mn) node[p].mn=id;
}
}
void reverseadd(string &x,int id)
{
int p=0;
for(int i=x.size()-1;i>=0;i--)
{
if(node[p].child[x[i]-'A']==-1) node[p].child[x[i]-'A']=++curtrieid;
//cout<<p<<" "<<node[p].child[x[i]-'A']<<" "<<x[i]<<el;
p=node[p].child[x[i]-'A'];
reverse_end[p].push_back(id);
}
}
int findd(string &x)
{
int p=0;
for(auto z : x)
{
if(node[p].child[z-'A']==-1) return 0;
p=node[p].child[z-'A'];
}
return p;
}
void solve()
{
int begin_node=findd(a);
reverse(b.begin(),b.end());
int end_node=findd(b);
if(!begin_node||!end_node)
{
cout<<0<<el;
return;
}
/*cout<<begin_node<<" "<<end_node<<el;
cout<<node[begin_node].mn<<" "<<node[begin_node].mx<<el;*/
int l=lower_bound(reverse_end[end_node].begin(), reverse_end[end_node].end(),node[begin_node].mn)-reverse_end[end_node].begin()+1;
int r=upper_bound(reverse_end[end_node].begin(), reverse_end[end_node].end(),node[begin_node].mx)-reverse_end[end_node].begin()+1;
cout<<max(0,r-l)<<el;
}
signed main()
{
ios_base::sync_with_stdio (false);
cin.tie(0); cout.tie(0);
//fre("NTHANH");
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>s[i];
sort(s+1,s+1+n);
for(int i=1;i<=n;i++)
{
add(s[i],i);
reverseadd(s[i],i);
}
while(m--)
{
cin>>a>>b;
solve();
}
return 0;
}
