#include <bits/stdc++.h>
using namespace std;
template<class T> bool ckmin(T &u, const T &v) { return u > v ? (u = v, true) : false; }
template<class T> bool ckmax(T &u, const T &v) { return u < v ? (u = v, true) : false; }
int conv(char c) {
if (c == 'A') return 0;
if (c == 'U') return 1;
if (c == 'G') return 2;
return 3;
}
struct prefix_trie {
typedef array<int, 4> node;
vector<node> tree;
vector<pair<int, int>> range;
prefix_trie() : tree(1, node{}), range(1, {int(1e9), -1}) {}
void insert(const string &s, int idx) {
int cur = 0;
for (int i = 0; i < (int)s.size(); i++) {
int c = conv(s[i]);
if (!tree[cur][c]) {
tree[cur][c] = (int)tree.size();
tree.push_back(node{});
range.push_back({int(1e9), -1});
}
cur = tree[cur][c];
ckmin(range[cur].first, idx);
ckmax(range[cur].second, idx);
}
}
pair<int, int> query(const string &s) {
int cur = 0;
for (int i = 0; i < (int)s.size(); i++) {
int c = conv(s[i]);
if (!tree[cur][c]) return {-1, -1};
cur = tree[cur][c];
}
return range[cur];
};
};
struct suffix_trie {
typedef array<int, 4> node;
vector<node> tree;
vector<vector<int>> indices;
suffix_trie() : tree(1, node{}), indices(1) {}
void insert(const string &s, int idx) {
int cur = 0;
for (int i = 0; i < (int)s.size(); i++) {
int c = conv(s[i]);
if (!tree[cur][c]) {
tree[cur][c] = (int)tree.size();
tree.push_back(node{});
indices.push_back(vector<int>());
}
cur = tree[cur][c];
indices[cur].push_back(idx);
}
}
vector<int> query(const string &s) {
int cur = 0;
for (int i = 0; i < (int)s.size(); i++) {
int c = conv(s[i]);
if (!tree[cur][c]) return vector<int>();
cur = tree[cur][c];
}
return indices[cur];
}
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, m; cin >> n >> m;
string word_list[n]; for (int i = 0; i < n; i++) cin >> word_list[i];
sort(word_list, word_list + n);
prefix_trie pfx;
suffix_trie sfx;
for (int i = 0; i < n; i++) {
pfx.insert(word_list[i], i);
reverse(word_list[i].begin(), word_list[i].end());
sfx.insert(word_list[i], i);
}
for (int i = 0; i < m; i++) {
string p, q; cin >> p >> q;
reverse(q.begin(), q.end());
auto t1 = pfx.query(p);
auto t2 = sfx.query(q);
auto j1 = lower_bound(t2.begin(), t2.end(), t1.first);
auto j2 = upper_bound(t2.begin(), t2.end(), t1.second);
cout << int(j2 - j1) << '\n';
}
}
