/* https://oj.uz/problem/view/JOI16_selling_rna */
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define bit(n,i) ((n>>i)&1)
#define Fup(i,x,y) for(i=x;i<=y;i++)
#define Fdo(i,x,y) for(i=x;i>=y;i--)
#define LOG 20
#define maxN 100005
using namespace std;
int n,m,i,cnt_01=0,cnt_02=0,res;
string s[maxN],t[maxN],p,q;
struct DATA_01{ int id,l,r; }trie_01[200005][26];
int trie_02[200005][26];
vector<int>X[200005];
void add_01(string& s,int ID){
int i,u,k;
u=0;
for(i=0;i<s.size();i++){
k=s[i]-'A';
if(trie_01[u][k].id==0){
++cnt_01;
trie_01[u][k]={cnt_01,ID,ID};
}
else{
trie_01[u][k].l=min(trie_01[u][k].l,ID);
trie_01[u][k].r=max(trie_01[u][k].r,ID);
}
u=trie_01[u][k].id;
}
return;
}
pair<int,int>get_01(string& s){
int i,u,k;
pair<int,int>res={1e9,-1e9};
u=0;
for(i=0;i<s.size();i++){
k=s[i]-'A';
if(trie_01[u][k].id==0)return {0,0};
res.fi=min(res.fi, trie_01[u][k].l );
res.se=max(res.se, trie_01[u][k].r );
u=trie_01[u][k].id;
}
return res;
}
void add_02(string& s,int ID){
int u,i,k;
u=0;
for(i=0;i<s.size();i++){
k=s[i]-'A';
if(trie_02[u][k]==0){ trie_02[u][k]=++cnt_02; }
u=trie_02[u][k];
X[u].push_back(ID);
}
}
vector<int> get_02(string& s){
int u,i,k;
u=0;
for(i=0;i<s.size();i++){
k=s[i]-'A';
if(trie_02[u][k]==0){ vector<int>I; I.clear(); return I; }
u=trie_02[u][k];
}
return X[u];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for(i=1;i<=n;i++) cin>>s[i];
sort(s+1,s+n+1);
for(i=1;i<=n;i++){
t[i]=s[i];
reverse(t[i].begin(),t[i].end());
}
for(i=1;i<=n;i++){
add_01(s[i],i);
add_02(t[i],i);
}
while(m--){
cin>>p>>q;
reverse(q.begin(),q.end());
auto T_01=get_01(p);
auto T_02=get_02(q);
res=upper_bound(T_02.begin(), T_02.end(), T_01.se)
- lower_bound(T_02.begin(), T_02.end(), T_01.fi);
cout<<res<<'\n';
}
return 0;
}
/*
3 3
AA
AA
AGA
AA AA
AG GA
AG GA
*/
