#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,q;
int child[2000001][26];
string z[1000005];
int cnt;
int mark[1000005];
int tour;
int sta[1000005];
int fin[1000005];
int ver[1000005];
vector<pair<int,int>> m;
int mod=1e9+7;
int base=43;
bool cmp(pair<int,int> a,pair<int,int> b){
if (a.first==b.first){
return a.second<b.second;
}
return a.first<b.first;
}
void add(string& s,int pos){
int k=0;
for (auto c:s){
if (!child[k][c-'A']){
cnt++;
child[k][c-'A']=cnt;
}
k=child[k][c-'A'];
}
mark[pos]=k;
}
void dfs(int k){
tour++;
sta[k]=tour;
ver[tour]=k;
for (int i=0;i<26;i++){
if (child[k][i]){
dfs(child[k][i]);
}
}
fin[k]=tour;
}
int get(string& s,long long val){
int k=0;
for (auto c:s){
if (!child[k][c-'A']){
return 0;
}
k=child[k][c-'A'];
}
// cout << "ok" << "\n";
// cout << m[val].size() << "\n";
int pos=sta[k];
int l=lower_bound(m.begin(),m.end(),make_pair(val,pos))-m.begin();
pos=fin[k];
int r=upper_bound(m.begin(),m.end(),make_pair(val,pos))-m.begin()-1;
return r-l+1;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> a >> q;
for (int i=1;i<=a;i++){
cin >> z[i];
add(z[i],i);
}
dfs(0);
for (int i=1;i<=a;i++){
long long h=0;
int pos=mark[i];
pos=sta[pos];
for (int j=z[i].size()-1;j>=0;j--){
h=(h*base + (z[i][j]-'A'+1))%mod;
// cout << h << " ";
m.push_back({h,pos});
}
}
sort(m.begin(),m.end(),cmp);
while (q--){
string s,s1;
cin >> s >> s1;
long long h=0;
for (int i=s1.size()-1;i>=0;i--){
h=(h*base + (s1[i]-'A'+1))%mod;
}
// cout << h << " ";
cout << get(s,h) << "\n";
}
return 0;
}
