#include <bits/stdc++.h>
using namespace std;
struct TrieNode {
array<int, 4> child;
vector<int> indices;
TrieNode() { child.fill(-1); }
};
const string letters = "AGCU";
int main() {
vector<TrieNode> node = {TrieNode()};
const auto get_path = [&](const string& word) {
int cur = 0;
vector<int> path;
for (const char c : word) {
for (int k = 0; k < 4; ++k) {
if (letters[k] == c) {
if (node[cur].child[k] == -1) {
node[cur].child[k] = size(node);
node.push_back(TrieNode());
}
cur = node[cur].child[k];
break;
}
}
path.push_back(cur);
}
return path;
};
int N, M;
cin >> N >> M;
vector<string> S(N);
for (auto& x : S) {
cin >> x;
reverse(begin(x), end(x));
}
sort(begin(S), end(S));
for (int i = 0; i < N; ++i) {
for (const int u : get_path(string(rbegin(S[i]), rend(S[i])))) {
node[u].indices.push_back(i);
}
}
while (M--) {
string P, Q;
cin >> P >> Q;
reverse(begin(Q), end(Q));
const auto& list = node[get_path(P).back()].indices;
const auto get = [&](const int k) {
return string(begin(S[k]), begin(S[k]) + min(size(S[k]), size(Q)));
};
const auto lowb =
partition_point(begin(list), end(list), [&](const int k) { return Q > get(k); });
const auto upb =
partition_point(begin(list), end(list), [&](const int k) { return Q >= get(k); });
cout << upb - lowb << '\n';
}
return 0;
}
