#include <bits/stdc++.h>
using namespace std;
struct Node {
Node* child[4];
vector<int> pre;
bool exist = false;
Node() { for (int i = 0; i < 4; ++i) child[i] = nullptr; }
};
struct Trie {
Node* root;
Trie() { root = new Node(); }
// s must consist of letters 'A'..'D' only (we use 0..3)
void add(const string &s, int idx) {
Node* p = root;
p->pre.push_back(idx);
for (char ch : s) {
int c = ch - 'A';
if (c < 0 || c > 3) return; // defensive (shouldn't happen)
if (!p->child[c]) p->child[c] = new Node();
p = p->child[c];
p->pre.push_back(idx);
}
p->exist = true;
}
// sort pre vectors in the whole trie
void sort_all(Node* p = nullptr) {
if (p == nullptr) p = root;
sort(p->pre.begin(), p->pre.end());
for (int i = 0; i < 4; ++i)
if (p->child[i]) sort_all(p->child[i]);
}
// find node representing string s (or nullptr)
Node* find_node(const string &s) {
Node* p = root;
for (char ch : s) {
int c = ch - 'A';
if (c < 0 || c > 3) return nullptr;
if (!p->child[c]) return nullptr;
p = p->child[c];
}
return p;
}
};
// map AGCU -> A,B,C,D so letters are 'A'..'D'
string trans(const string &inp) {
string out;
out.reserve(inp.size());
for (char ch : inp) {
if (ch == 'A') out.push_back('A');
else if (ch == 'G') out.push_back('B');
else if (ch == 'C') out.push_back('C');
else if (ch == 'U') out.push_back('D');
else {
// if there are lowercase or T etc, you may want to handle or convert
out.push_back(ch); // defensive
}
}
return out;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// optional file redir for local:
// if (fopen("DELSEQ.INP", "r")) { freopen("DELSEQ.INP", "r", stdin); freopen("DELSEQ.OUT", "w", stdout); }
int n, m;
if (!(cin >> n >> m)) return 0;
Trie tPref, tSuf; // tPref -> prefixes; tSuf -> reversed strings (to handle suffixes)
vector<string> arr(n + 1);
for (int i = 1; i <= n; ++i) {
string tmp; cin >> tmp;
string tr = trans(tmp);
arr[i] = tr;
// add to prefix trie with index i
tPref.add(tr, i);
// add reversed string to suffix trie with index i
reverse(tr.begin(), tr.end());
tSuf.add(tr, i);
}
// sort all pre vectors so lower_bound/upper_bound work
tPref.sort_all();
tSuf.sort_all();
while (m--) {
string p, q; cin >> p >> q;
p = trans(p);
q = trans(q);
// find prefix node in tPref
Node* nodeP = tPref.find_node(p);
if (nodeP == nullptr || nodeP->pre.empty()) {
cout << 0 << '\n';
continue;
}
int L = nodeP->pre.front(); // minimum original index with prefix p
int R = nodeP->pre.back(); // maximum original index with prefix p
// find suffix node in reversed trie (we must reverse q)
reverse(q.begin(), q.end());
Node* nodeQ = tSuf.find_node(q);
if (nodeQ == nullptr || nodeQ->pre.empty()) {
cout << 0 << '\n';
continue;
}
// count how many indices in nodeQ->pre fall into [L, R]
auto &vec = nodeQ->pre;
int lp = int(lower_bound(vec.begin(), vec.end(), L) - vec.begin());
int rp = int(upper_bound(vec.begin(), vec.end(), R) - vec.begin());
cout << (rp - lp) << '\n';
}
return 0;
}
