#include <bits/stdc++.h>
using namespace std;
#define pii array<int,2>
struct Node {
vector<int> cld = vector<int>(26, -1);
pii inv;
int startThis = -1;
int cntEnd=0;
};
struct Node2 {
vector<int> cld=vector<int>(26, -1);
vector<int> tourIdx;
};
Node root;
vector<Node> trie = {root};
Node2 root2;
vector<Node2> trie2 = {root2};
void insert(string &s) {
int idx = 0;
for (int i=0;i<(int)s.size();i++) {
// cout<<i<<endl;
int cc = (s[i]-'A');
// cout<<cc<<endl;
if (trie[idx].cld[s[i]-'A'] == -1) {
Node n1;
trie[idx].cld[s[i]-'A'] = (int)trie.size();
trie.push_back(n1);
}
// cout<<"here"<<endl;
idx = trie[idx].cld[s[i]-'A'];
}
trie[idx].cntEnd++;
}
void insert2(string &t, int order) {
int idx = 0;
trie2[idx].tourIdx.push_back(order);
for (int i=(int)t.size()-1;i>=0;i--) {
if (trie2[idx].cld[t[i]-'A'] == -1) {
Node2 n1;
trie2[idx].cld[t[i]-'A'] = (int)trie2.size();
trie2.push_back(n1);
}
idx = trie2[idx].cld[t[i]-'A'];
trie2[idx].tourIdx.push_back(order);
}
}
int counter = 0;
string tt;
void trav(int idx) {
trie[idx].inv[0] = counter;
if (trie[idx].cntEnd) {
trie[idx].startThis = counter;
for (int i=trie[idx].startThis;i<trie[idx].startThis+trie[idx].cntEnd;i++) {
insert2(tt, i);
}
}
counter += trie[idx].cntEnd;
for (int i=0;i<26;i++) {
if (trie[idx].cld[i] != -1) {
tt += string(1, i+'A');
trav(trie[idx].cld[i]);
tt.pop_back();
}
}
trie[idx].inv[1] = counter-1;
}
pii search1(string &s) {
int idx = 0;
for (int i=0;i<(int)s.size();i++) {
if (trie[idx].cld[s[i]-'A'] == -1) {
return {-1, -1};
}
idx=trie[idx].cld[s[i]-'A'];
}
return trie[idx].inv;
}
int search2(string &t, pii inv) {
int idx = 0;
for (int i=(int)t.size()-1;i>=0;i--) {
if (trie2[idx].cld[t[i]-'A'] == -1) return 0;
idx = trie2[idx].cld[t[i]-'A'];
}
auto it=lower_bound(trie2[idx].tourIdx.begin(), trie2[idx].tourIdx.end(), inv[0]);
if (*it > inv[1]) {
return 0;
}
int pos1 = distance(trie2[idx].tourIdx.begin(), it);
auto it2=upper_bound(trie2[idx].tourIdx.begin(), trie2[idx].tourIdx.end(), inv[1]);
it2 = prev(it2);
int pos2 = distance(trie2[idx].tourIdx.begin(), it2);
return pos2-pos1+1;
}
signed main() {
int n,m;cin>>n>>m;
while (n--) {
string s;cin>>s;
// cout<<n<<endl;
insert(s);
}
// cout<<"here"<<endl;
// cout.flush();
trav(0);
// cout<<"here"<<endl;
// cout.flush();
while (m--) {
string s,t;cin>>s>>t;
pii inv=search1(s);
if (inv[0]==-1) {
cout<<0<<endl;
continue;
}
cout<<search2(t,inv)<<endl;
}
}
