// https://oj.uz/problem/view/JOI16_selling_rna
#include <bits/stdc++.h>
using namespace std;
struct trie {
vector<vector<int>> child {{-1, -1, -1, -1}};
vector<vector<int>> s {{}};
vector<vector<int>> ns {{}};
vector<vector<int>> q {{}};
vector<int> sz {0};
vector<int> cnt {0};
};
vector<int> toc (26, -1);
vector<string> vs;
vector<string> vsr;
vector<string> vp;
vector<string> vq;
trie pref {};
void insert (trie &t, bool isq,bool iscnt, int &px, int szx, string &s, int id = 0, int i = 0) {
if (!isq) {
t.sz[i] += szx;
t.s[i].push_back(px);
}
if (iscnt) t.cnt[i] += 1;
if (id == s.size()) {
if (isq) {
t.q[i].push_back(px);
} else {
t.ns[i].push_back(px);
}
return;
}
int c = toc[s[id] - 'A'];
if (t.child[i][c] == -1) {
if (isq && !iscnt) return;
t.child.push_back({-1, -1, -1, -1});
t.s.push_back({});
t.q.push_back({});
t.sz.push_back(0);
t.cnt.push_back(0);
t.ns.push_back({});
t.child[i][c] = t.child.size() - 1;
}
insert(t, isq, iscnt, px, szx, s, id+1, t.child[i][c]);
}
int query (trie &t, string&s, int id = 0, int i = 0) {
if (id == s.size()) return t.cnt[i];
int c = toc[s[id] - 'A'];
if (t.child[i][c] == -1) return 0;
else return query(t, s, id+1, t.child[i][c]);
}
vector<trie> dp;
vector<int> sol;
void comp (int i) {
int max_sub = -1;
int max_val = 1e9;
for (int c = 0; c < 4; c++) {
if (pref.child[i][c] != -1) {
comp(pref.child[i][c]);
if (pref.sz[i] > max_val) {
max_val = pref.sz[i];
max_sub = i;
}
}
}
if (max_sub != -1) {
swap(dp[i], dp[pref.child[i][max_sub]]);
}
for (int c = 0; c < 4; c++) {
if (c == max_sub) continue;
if (pref.child[i][c] == -1) continue;
dp[pref.child[i][c]] = {};
for (auto &it : pref.s[pref.child[i][c]]) {
insert(dp[i], true, true, it, 0, vsr[it]);
}
}
for (auto &it : pref.ns[i]) {
insert(dp[i], true, true, it, 0, vsr[it]);
}
for (auto &it : pref.q[i]) {
sol[it] = query(dp[i], vq[it]);
}
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
toc['A' - 'A'] = 0;
toc['G' - 'A'] = 1;
toc['C' - 'A'] = 2;
toc['U' - 'A'] = 3;
int n, m;
cin >> n >> m;
vs = vector<string> (n);
vsr = vector<string> (n);
for (int i = 0; i < n; i++) {
cin >> vs[i];
vsr[i] = vs[i];
reverse(vsr[i].begin(), vsr[i].end());
insert(pref, false, true, i, vs[i].size(), vs[i]);
}
vp = vector<string> (m);
vq = vector<string> (m);
for (int i = 0; i < m; i++) {
cin >> vp[i] >> vq[i];
reverse(vq[i].begin(), vq[i].end());
insert(pref, true, false, i, vq[i].size(), vp[i]);
}
sol = vector<int> (m, 0);
dp = vector<trie> (pref.child.size());
comp(0);
for (int i = 0; i < m; i++) {
cout << sol[i] << "\n";
}
return 0;
}
