//source:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int get(const char &c) {
if (c == 'A') return 0;
if (c == 'G') return 1;
if (c == 'C') return 2;
return 3;
}
struct Trie {
Trie* child[4];
int mx, mi;
Trie () {
child[0] = child[1] = child[2] = child[3] = nullptr;
mx = 0, mi = 1e9;
}
};
Trie *root = new Trie();
void add(const string &s, int idx) {
Trie *p = root;
for (const char &i : s) {
int x = get(i);
if (!p -> child[x]) p -> child[x] = new Trie();
p = p -> child[x];
p -> mx = max(p -> mx, idx);
p -> mi = min(p -> mi, idx);
}
}
pair<int, int> get(const string &s) {
Trie *p = root;
for (const char &i : s) {
int x = get(i);
if (!p -> child[x]) return make_pair(-1, 0);
p = p -> child[x];
}
return make_pair(p -> mi, p -> mx);
}
struct RevTrie {
RevTrie* child[4];
vector<int> pos;
RevTrie () {
child[0] = child[1] = child[2] = child[3] = nullptr;
}
};
RevTrie *RevRoot = new RevTrie();
void RevAdd(const string &s, int idx) {
RevTrie *p = RevRoot;
for (const char &i : s) {
int x = get(i);
if (!p -> child[x]) p -> child[x] = new RevTrie();
p = p -> child[x];
p -> pos.push_back(idx);
}
}
int get(const string &s, int L, int R) {
RevTrie *p = RevRoot;
for (const char &i : s) {
int x = get(i);
if (!p -> child[x]) return 0;
p = p -> child[x];
}
return upper_bound(p -> pos.begin(), p -> pos.end(), R) - lower_bound(p -> pos.begin(), p -> pos.end(), L);
}
const int N = 1e5 + 10;
string a[N];
signed main() {
cin.tie(0)->sync_with_stdio(0);
if (fopen("JOI16_selling_rna.inp", "r")) {
freopen("JOI16_selling_rna.inp", "r", stdin);
freopen("JOI16_selling_rna.out", "w", stdout);
}
#ifdef LOCAL_MACHINE
if (fopen("task.inp", "r")) {
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
}
#endif
int n, q; cin >> n >> q;
for (int i = 1; i <= n; ++i) cin >> a[i];
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; ++i) add(a[i], i);
for (int i = 1; i <= n; ++i) reverse(a[i].begin(), a[i].end());
for (int i = 1; i <= n; ++i) RevAdd(a[i], i);
while (q--) {
string P, Q; cin >> P >> Q;
int L, R; tie(L, R) = get(P);
if (!~L) {
cout << "0\n";
continue;
}
reverse(Q.begin(), Q.end());
cout << get(Q, L, R) << "\n";
}
}
// ඞඞඞඞඞ you sus
