#include <bits/stdc++.h>
using namespace std;
void Transform(string &s) {
for (auto &i : s) {
if (i == 'A') i = '0';
if (i == 'G') i = '1';
if (i == 'C') i = '2';
if (i == 'U') i = '3';
}
}
class Trie {
private:
struct Node {
int sz = 0;
int nxt[4] = {-1, -1, -1, -1};
Node() {}
};
vector<Node> trie = vector<Node>(1);
public:
Trie() {}
vector<string> strings;
void Insert(const string &s) {
strings.emplace_back(s);
int cur = 0;
trie[cur].sz++;
for (const auto &c : s) {
if (trie[cur].nxt[c - '0'] == -1) {
trie[cur].nxt[c - '0'] = trie.size();
trie.emplace_back();
}
cur = trie[cur].nxt[c - '0'];
trie[cur].sz++;
}
}
int Count(const string &s) {
int cur = 0;
for (const auto &c : s) {
if (cur == -1) break;
cur = trie[cur].nxt[c - '0'];
}
if (cur == -1) {
return 0;
} else {
return trie[cur].sz;
}
}
};
class SegmentTree {
private:
int sz;
vector<Trie> tree;
public:
SegmentTree(const vector<string> &s) {
sz = s.size();
tree.resize(2 * sz);
for (int i = 0; i < sz; i++) {
tree[i + sz].Insert(s[i]);
}
for (int i = sz - 1; i > 0; i--) {
for (const auto &j : tree[i * 2].strings) {
tree[i].Insert(j);
}
for (const auto &j : tree[i * 2 + 1].strings) {
tree[i].Insert(j);
}
}
}
int Query(int l, int r, const string &s) {
int res = 0;
for (l += sz, r += sz; l < r; l /= 2, r /= 2) {
if (l & 1) res += tree[l++].Count(s);
if (r & 1) res += tree[--r].Count(s);
}
return res;
}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int N, M;
cin >> N >> M;
vector<string> strings(N);
for (int i = 0; i < N; i++) {
cin >> strings[i];
Transform(strings[i]);
}
sort(begin(strings), end(strings));
for (int i = 0; i < N; i++) reverse(begin(strings[i]), end(strings[i]));
SegmentTree seg(strings);
for (int i = 0; i < N; i++) reverse(begin(strings[i]), end(strings[i]));
for (int i = 0; i < M; i++) {
string P, Q;
cin >> P >> Q;
Transform(P), Transform(Q);
reverse(begin(Q), end(Q));
int l = lower_bound(begin(strings), end(strings), P) - begin(strings);
P.push_back('5');
int r = lower_bound(begin(strings), end(strings), P) - begin(strings);
P.pop_back();
cout << seg.Query(l, r, Q) << "\n";
}
return 0;
}
