#include <bits/stdc++.h>
using namespace std;
int c[256];
class trie_t {
public:
int l, r, is_sorted;
vector<int> index;
trie_t* g[4];
trie_t() {
l = 1e9, r = -1, is_sorted = 0;
for (int i = 0; i < 4; i++) g[i] = nullptr;
}
static void add(trie_t* root, const string& s, int id) {
for (auto&& x : s) {
if (!root->g[c[x]]) {
root->g[c[x]] = new trie_t();
}
root = root->g[c[x]];
root->index.emplace_back(id);
root->l = min(root->l, id);
root->r = max(root->r, id);
}
}
static pair<int, int> get(trie_t* root, const string& s) {
for (auto&& x : s) {
if (!root->g[c[x]]) {
return {-1, -1};
}
root = root->g[c[x]];
}
return {root->l, root->r};
}
static int solve(trie_t* root, int l, int r, const string& s) {
for (auto&& x : s) {
if (!root->g[c[x]]) {
return 0;
}
root = root->g[c[x]];
}
if (!root->is_sorted) sort(root->index.begin(), root->index.end()), root->is_sorted = 1;
return upper_bound(root->index.begin(), root->index.end(), r) - lower_bound(root->index.begin(), root->index.end(), l);
}
};
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
c['A'] = 0, c['G'] = 1, c['C'] = 2, c['U'] = 3;
int n, m;
cin >> n >> m;
vector<string> a(n), b(m);
for (int i = 0; i < n; i++) cin >> a[i];
sort(a.begin(), a.end());
trie_t* tree = new trie_t();
trie_t* rev_tree = new trie_t();
for (int i = 0; i < n; i++) trie_t::add(tree, a[i], i);
for (int i = 0; i < n; i++) reverse(a[i].begin(), a[i].end());
for (int i = 0; i < n; i++) trie_t::add(rev_tree, a[i], i);
for (int i = 0; i < m; i++) {
string p, q;
cin >> p >> q;
reverse(q.begin(), q.end());
auto [l, r] = trie_t::get(tree, p);
cout << (l <= r ? trie_t::solve(rev_tree, l, r, q) : 0) << '\n';
}
}
