#include <bits/stdc++.h>
#define Pc_champs ios_base::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
using namespace std;
#define ll long long
//#define int long long
int const N = 1e5 + 2, LOG = 17, N2 = 1e5, M = 1e9 + 7, SQ = 400;
int n, m, idx;
string s[N];
int id[26];
struct Trie {
struct Node {
Node *link[4];
vector<int> indx;
};
Node *root = NULL;
Trie() {
root = new Node();
}
void insert(string &str, int j) {
Node *node = root;
for (auto i: str) {
i -= 'A';
if (node->link[id[i]] == NULL) node->link[id[i]] = new Node();
node = node->link[id[i]];
node->indx.emplace_back(j);
}
}
pair<int, int> rng(string &lft) {
Node *node = root;
for (auto i: lft) {
i -= 'A';
if (node->link[id[i]] == NULL) return {-1, -1};
node = node->link[id[i]];
}
return {node->indx[0], node->indx.back()};
}
int get(string &rgt, int l, int r) {
Node *node = root;
for (auto &i: rgt) {
i -= 'A';
if (node->link[id[i]] == NULL) return 0;
node = node->link[id[i]];
}
return lower_bound(node->indx.begin(), node->indx.end(), r + 1) -
lower_bound(node->indx.begin(), node->indx.end(), l);
}
};
void dowork() {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
id[0] = 0;
id['C' - 'A'] = 1;
id['G' - 'A'] = 2;
id['U' - 'A'] = 3;
sort(s, s + n);
Trie t1 = Trie(), t2 = Trie();
for (int i = 0; i < n; ++i) {
t1.insert(s[i], i);
}
for (int i = 0; i < n; ++i) {
reverse(s[i].begin(), s[i].end());
t2.insert(s[i], i);
}
while (m--) {
string S, P;
cin >> S >> P;
reverse(P.begin(), P.end());
pair<int, int> p = t1.rng(S);
if (p.first == -1) {
cout << 0;
} else {
cout << t2.get(P, p.first, p.second);
}
cout << '\n';
}
}
signed main() {
Pc_champs
int t = 1;
//cin >> t;
while (t--) {
++idx;
dowork();
//cout << "\n";
}
}
