#include <bits/stdc++.h>
using namespace std;
int n, m; struct pi { int l, r; };
int ctoi(char a) {
if (a=='A') return 0;
if (a=='G') return 1;
if (a=='C') return 2;
return 3;
}
static char buf[450 << 20];
void* operator new(size_t s) {
static size_t i = sizeof buf;
assert(s < i); return (void*)&buf[i -= s];
}
void operator delete(void*) noexcept {}
struct PTrie {
int l = 0, r = 1e5+1;
PTrie* ch[4]={nullptr, nullptr, nullptr, nullptr};
void insert(string &a, int si, int i) {
if (si==a.size()) { return; }
int nx = ctoi(a[si]);
if (!ch[nx]) ch[nx] = new PTrie{}, ch[nx]->r = ch[nx]->l = i;
else ch[nx]->r = i; // i will always be the latest we have seen
ch[nx]->insert(a, si+1, i);
}
pi prefix(string &a, int si) {
if (si==a.size()) return {l, r};
int nx = ctoi(a[si]);
if (ch[nx]) return ch[nx]->prefix(a, si+1);
else return {-1, -1};
}
};
struct QTrie {
vector<int> ss; bool std = false;
QTrie* ch[4]={nullptr, nullptr, nullptr, nullptr};
void insert(string &a, int si, int i) {
if (si==a.size()) { return; }
int nx = ctoi(a[si]);
if (!ch[nx]) ch[nx] = new QTrie{};
ch[nx]->ss.push_back(i);
ch[nx]->insert(a, si+1, i);
}
int prefix(string &a, int si, int l, int r) {
if (si==a.size()) {
if (!std) sort(begin(ss), end(ss)), std = true;
return upper_bound(begin(ss), end(ss), r)-lower_bound(begin(ss), end(ss), l);
}
int nx = ctoi(a[si]);
if (ch[nx]) return ch[nx]->prefix(a, si+1, l, r);
else return 0;
}
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> m; vector<string> S(n);
PTrie pt; QTrie qt;
for (int i=0;i<n;i++) cin >> S[i];
sort(begin(S), end(S));
for (int i=0;i<n;i++) pt.insert(S[i], 0, i), reverse(begin(S[i]), end(S[i])), qt.insert(S[i], 0, i);
for (int i=0;i<m;i++) {
string p, q; cin >> p >> q; reverse(begin(q), end(q));
auto [l, r] = pt.prefix(p, 0);
cout << qt.prefix(q, 0, l, r) << '\n';
}
}
