#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
string en[1<<17], st, s;
int Ans[1<<17], mod = 998244353;
vector<int> hsh[1<<17];
struct node{
vector<int> vc;
vector<node*> ch;
char cur;
void insert(string &s, int ind, int vl){
vc.push_back(vl);
if (ind == s.size())
return;
for (int i=0;i<ch.size();i++){
if (ch[i]->cur == s[ind]){
ch[i]->insert(s, ind+1, vl);
return;
}
}
node* Nw = new node();
Nw->cur = s[ind];
ch.push_back(Nw);
Nw->insert(s, ind+1, vl);
}
int get(string &s, int ind, int vl){
if (ind == s.size()){
int l = -1, r = vc.size();
while (l + 1 < r){
int mid = (l + r) / 2;
if (vc[mid] <= vl)
r = mid;
else
l = mid;
}
return vc.size() - r;
}
for (int i=0;i<ch.size();i++){
if (ch[i]->cur == s[ind])
return ch[i]->get(s, ind+1, vl);
}
return 0;
}
};
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n, m;
cin>>n>>m;
vector<pair<string, int>> vec;
for (int i=1;i<=n;i++){
cin>>s;
vec.push_back({s, i});
}
for (int i=1;i<=m;i++){
cin>>st>>en[i];
reverse(begin(en[i]), end(en[i]));
vec.push_back({st, -i});
}
sort(begin(vec), end(vec));
node *rt = new node();
for (int i=vec.size()-1, id = n;i>=0;i--){
if (vec[i].second < 0){
int h = 0;
s = vec[i].first;
for (int j=0;j<s.size();j++)
h = (1LL * h * 256 + s[j]) % mod;
int l = id, r = n + 1;
while (l + 1 < r){
int mid = (l + r) / 2;
if (hsh[mid].size() >= s.size() and hsh[mid][s.size() - 1] == h)
l = mid;
else
r = mid;
}
Ans[-vec[i].second] = rt->get(en[-vec[i].second], 0, l);
}
else{
s = vec[i].first;
for (int j=0, h = 0;j<s.size();j++)
h = (1LL * h * 256 + s[j]) % mod, hsh[id].push_back(h);
reverse(begin(s), end(s));
rt->insert(s, 0, id);
id--;
}
}
for (int i=1;i<=m;i++)
cout<<Ans[i]<<' ';
cout<<'\n';
}
