#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cstring>
using namespace std;
unordered_map<char, int> id = {{'A', 0}, {'C', 1}, {'G', 2}, {'U', 3}};
struct Node {
int children[4];
vector<int> e;
Node() {
memset(children, -1, sizeof(children));
}
};
struct Trie {
vector<Node> trie;
Trie() {
trie = {Node()};
}
void insert(const string& s, int x) {
int node = 0, sz = s.size();
trie[node].e.push_back(x);
for (int i = 0; i < sz; i++) {
if (trie[node].children[id[s[i]]] == -1) {
trie[node].children[id[s[i]]] = trie.size();
trie.push_back(Node());
}
node = trie[node].children[id[s[i]]];
trie[node].e.push_back(x);
}
}
pair<int, int> getRange(const string& s) {
int node = 0, sz = s.size();
for (int i = 0; i < sz; i++) {
if (trie[node].children[id[s[i]]] == -1) return {-1, -1};
node = trie[node].children[id[s[i]]];
}
return {trie[node].e.front(), trie[node].e.back()};
}
int countElementsInRange(const string& s, pair<int, int> p) {
int l = p.first, r = p.second;
int node = 0, sz = s.size();
for (int i = 0; i < sz; i++) {
if (trie[node].children[id[s[i]]] == -1) return 0;
node = trie[node].children[id[s[i]]];
}
return upper_bound(trie[node].e.begin(), trie[node].e.end(), r) - lower_bound(trie[node].e.begin(), trie[node].e.end(), l);
}
};
int n, m;
vector<pair<string, string>> s;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
s.resize(n);
for (int i = 0; i < n; i++) {
cin >> s[i].first;
s[i].second = s[i].first;
reverse(s[i].second.begin(), s[i].second.end());
}
sort(s.begin(), s.end(), [](const pair<string, string>& p1, const pair<string, string>& p2) {
return p1.first < p2.first;
});
Trie trie_pref = Trie();
Trie trie_suf = Trie();
for (int i = 0; i < n; i++) {
trie_pref.insert(s[i].first, i);
trie_suf.insert(s[i].second, i);
}
for (int i = 0; i < m; i++) {
string pref, suf;
cin >> pref >> suf;
reverse(suf.begin(), suf.end());
pair<int, int> range = trie_pref.getRange(pref);
if (range.first == -1) {
cout << 0 << '\n';
} else {
cout << trie_suf.countElementsInRange(suf, range) << '\n';
}
}
return 0;
}
