#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int MMM=2e6+5;
int n,request,res;
string P;
string s[N];
namespace sub4
{
const int root=0;
struct Node
{
int cnt,nxt[26];
Node()
{
cnt=0;
memset(nxt,-1,sizeof(nxt));
}
};
vector <Node> trie,Rev_trie;
int save;
int sz[MMM],hld[MMM],ans[N];
string Q[N];
vector <int> add[MMM],query[MMM];
void init(string &s,int id,int pos)
{
sz[id]++;
trie[id].cnt++;
if (pos==s.size())
{
add[id].emplace_back(save);
return;
}
char c=s[pos]-'A';
if (trie[id].nxt[c]==-1)
{
trie[id].nxt[c]=trie.size();
trie.emplace_back(Node());
}
init(s,trie[id].nxt[c],pos+1);
if (hld[id]==0 or sz[hld[id]]<sz[trie[id].nxt[c]])
hld[id]=trie[id].nxt[c];
}
void add_queries(string &s,int id,int pos)
{
if (pos==s.size())
{
query[id].push_back(save);
return;
}
char c=s[pos]-'A';
if (trie[id].nxt[c]==-1) return;
add_queries(s,trie[id].nxt[c],pos+1);
}
void update_Revstring(string &s,int id,int pos,int neg)
{
Rev_trie[id].cnt+=neg;
if (pos<0) return;
char c=s[pos]-'A';
if (Rev_trie[id].nxt[c]==-1)
{
Rev_trie[id].nxt[c]=Rev_trie.size();
Rev_trie.emplace_back(Node());
}
update_Revstring(s,Rev_trie[id].nxt[c],pos-1,neg);
}
void Update_backstring(int id,int neg)
{
for (int j=0;j<26;j++)
if (trie[id].nxt[j]!=-1) Update_backstring(trie[id].nxt[j],neg);
for (int j:add[id])
update_Revstring(s[j],root,s[j].size()-1,neg);
}
int Get_revstring(string &s,int id,int pos)
{
if (pos<0) return Rev_trie[id].cnt;
char c=s[pos]-'A';
if (Rev_trie[id].nxt[c]==-1) return 0;
return Get_revstring(s,Rev_trie[id].nxt[c],pos-1);
}
void solve(int id)
{
if (hld[id]!=0)
{
for (int j=0;j<26;j++)
if (trie[id].nxt[j]!=-1 and trie[id].nxt[j]!=hld[id])
{
solve(trie[id].nxt[j]);
Update_backstring(trie[id].nxt[j],-1);
}
solve(hld[id]);
for (int j=0;j<26;j++)
if (trie[id].nxt[j]!=-1 and trie[id].nxt[j]!=hld[id])
Update_backstring(trie[id].nxt[j],1);
}
for (int j:add[id])
update_Revstring(s[j],root,s[j].size()-1,1);
for (int j:query[id])
ans[j]=Get_revstring(Q[j],root,Q[j].size()-1);
}
void solve()
{
trie.emplace_back(Node());
Rev_trie.emplace_back(Node());
for (int i=1;i<=n;i++)
{
save=i;
init(s[i],root,0);
}
for (int i=1;i<=request;i++)
{
cin >> P >> Q[i];
save=i;
add_queries(P,root,0);
}
solve(root);
for (int i=1;i<=request;i++)
cout << ans[i] << '\n';
}
}
int main()
{
ios_base::sync_with_stdio(NULL);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> request;
for (int i=1;i<=n;i++)
cin >> s[i];
sub4::solve();
}
