#include <stdio.h>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
using namespace std;
#define pb push_back
const int H=100050;
const int N=2000050;
const int M=2*N;
map<char,int> go[M];
vector<int> my[M],all[H];
int tsz,root[2],lid[M],rid[M],tid,fir[M],las[M];
void Insert(int &c, int lvl, int n, char *s, int id)
{
if(!c) c=++tsz;
if(lvl==n){ my[c].pb(id);all[id].pb(c);return;}
Insert(go[c][s[0]],lvl+1,n,s+1,id);
}
int Find(int c, int lvl, int n, char *s)
{
if(lvl==n) return c;
return Find(go[c][s[0]],lvl+1,n,s+1);
}
vector<int> ord;
int id[H];
void DFS1(int c)
{
int i;
map<char,int>::iterator it;
fir[c]=ord.size()+1;
for(i=0;i<my[c].size();i++) ord.pb(my[c][i]),id[my[c][i]]=ord.size();
for(it=go[c].begin();it!=go[c].end();it++) DFS1(it->second);
las[c]=ord.size();
}
void DFS2(int c)
{
lid[c]=++tid;
map<char,int>::iterator it;
for(it=go[c].begin();it!=go[c].end();it++) DFS2(it->second);
rid[c]=tid;
}
vector<int> push[M];
int ls[M],rs[M],rt,csz;
void Set(int &c, int ss, int se, int qi, int id)
{
if(!c) c=++csz;
push[c].pb(id);
if(ss==se) return;
int mid=ss+se>>1;
if(qi<=mid) Set(ls[c],ss,mid,qi,id);
else Set(rs[c],mid+1,se,qi,id);
}
int Get(int c, int l, int r)
{
return upper_bound(push[c].begin(),push[c].end(),r)-lower_bound(push[c].begin(),push[c].end(),l);
}
int Get(int c, int ss, int se, int qs, int qe, int l, int r)
{
if(qs>se || ss>qe) return 0;
if(qs<=ss && qe>=se) return Get(c,l,r);
int mid=ss+se>>1;
return Get(ls[c],ss,mid,qs,qe,l,r)+Get(rs[c],mid+1,se,qs,qe,l,r);
}
char s[N],t[N];
int main()
{
int n,q,i;
scanf("%i %i",&n,&q);
for(i=1;i<=n;i++)
{
scanf("%s",s);
int len=strlen(s);
Insert(root[0],0,len,s,i);
reverse(s,s+len);
Insert(root[1],0,len,s,i);
}
DFS1(root[0]);
DFS2(root[1]);
for(i=0;i<ord.size();i++)
{
int j=ord[i];
Set(rt,1,N,lid[all[j].back()],id[j]);
//printf("Set: %i -> %i\n",lid[all[j].back()],id[j]);
}
while(q--)
{
scanf("%s %s",s,t);
int len1=strlen(s);
int len2=strlen(t);
reverse(t,t+len2);
int node1=Find(root[0],0,len1,s);
int node2=Find(root[1],0,len2,t);
//printf("node1:%i node2:%i\n",node1,node2);
//printf("Get: (%i %i) (%i %i)\n",lid[node2],rid[node2],fir[node1],las[node1]);
printf("%i\n",Get(rt,1,N,lid[node2],rid[node2],fir[node1],las[node1]));
}
return 0;
}
