#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
struct node
{
int x,id,type;
node(int _x = 0,int _id = 0,int _type = 0)
{
x = _x; id = _id; type = _type;
}
};
int n,m,sz;
int ans[maxn];
int pos[maxn];
int l[maxn];
int r[maxn];
int tree[maxn*4];
vector<node> p;
vector<node> q;
vector<string> s;
vector<string> t;
bool cmp1(node p1,node p2)
{
if(s[p1.x]==s[p2.x]) return p1.type<p2.type;
return s[p1.x]<s[p2.x];
}
bool cmp2(node p1,node p2)
{
if(t[p1.x]==t[p2.x]) return p1.type<p2.type;
return t[p1.x]<t[p2.x];
}
void add(int x,int val)
{
while(x<=sz)
{
tree[x] += val;
x += x&-x;
}
}
int sum(int x)
{
int res = 0;
while(x>0)
{
res += tree[x];
x -= x&-x;
}
return res;
}
main()
{
int i,x;
string temp,temp2;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
sz = 0;
for(i=0;i<n;i++)
{
cin >> temp;
s.push_back(temp); p.push_back(node(sz,i,0));
reverse(temp.begin(),temp.end());
t.push_back(temp); q.push_back(node(sz,i,0));
sz += 1;
}
for(i=0;i<m;i++)
{
cin >> temp >> temp2;
s.push_back(temp); p.push_back(node(sz,i,-1));
temp[temp.size()-1]++;
s.push_back(temp); p.push_back(node(sz+1,i,1));
reverse(temp2.begin(),temp2.end());
t.push_back(temp2); q.push_back(node(sz,i,-1));
temp2[temp2.size()-1]++;
t.push_back(temp2); q.push_back(node(sz+1,i,1));
sz += 2;
}
sort(&p[0],&p[sz],cmp1);
sort(&q[0],&q[sz],cmp2);
for(i=0;i<p.size();i++)
{
if(p[i].type==-1) l[p[i].id] = i+1;
if(p[i].type==0) pos[p[i].id] = i+1;
if(p[i].type==1) r[p[i].id] = i+1;
}
for(i=0;i<q.size();i++)
{
x = q[i].id;
if(q[i].type==-1) ans[x] -= sum(r[x])-sum(l[x]);
if(q[i].type==0) add(pos[x],1);
if(q[i].type==1) ans[x] += sum(r[x])-sum(l[x]);
}
for(i=0;i<m;i++) cout << ans[i] << endl;
}
