#include <bits/stdc++.h>
using namespace std;
const int N = (int) 1e5 + 7;
int decode(char ch) {
if (ch == 'A') return 0;
if (ch == 'G') return 1;
if (ch == 'C') return 2;
if (ch == 'U') return 3;
assert(false);
}
struct TrieNode {
TrieNode* kids[4];
int first;
int last;
vector<int> guys;
TrieNode() {
for (int i = 0; i < 4; i++) {
kids[i] = nullptr;
}
}
};
void addToTrie(TrieNode* root, string s, int index) {
TrieNode* current = root;
for (auto &ch : s) {
int decoded = decode(ch);
if (!current->kids[decoded]) {
current->kids[decoded] = new TrieNode;
}
current = current->kids[decoded];
}
current->guys.push_back(index);
}
void prepTrie(TrieNode* root, int inverse[]) {
int index = 0;
function<void(TrieNode*)> dfs = [&] (TrieNode* current) {
current->first = ++index;
for (auto &i : current->guys) {
inverse[i] = index;
}
for (int j = 0; j < 4; j++) {
if (current->kids[j]) {
dfs(current->kids[j]);
}
}
current->last = index;
};
dfs(root);
}
pair<int, int> getInterval(TrieNode* root, string s) {
TrieNode* current = root;
for (auto &ch : s) {
int decoded = decode(ch);
if (!current->kids[decoded]) {
return {1, 0};
}
current = current->kids[decoded];
}
return {current->first, current->last};
}
TrieNode* root1 = new TrieNode;
TrieNode* root2 = new TrieNode;
int x[N];
int y[N];
struct BBox {
int xmin;
int ymin;
int xmax;
int ymax;
int index;
};
int solPrint[N];
int main() {
bool isHome;
isHome = true;
isHome = false;
if (isHome) {
freopen ("input", "r", stdin);
} else {
ios::sync_with_stdio(0); cin.tie(0);
}
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
string s, revS;
cin >> s;
revS = s;
reverse(revS.begin(), revS.end());
addToTrie(root1, s, i);
addToTrie(root2, revS, i);
}
prepTrie(root1, x);
prepTrie(root2, y);
vector<BBox> bboxes;
for (int iq = 1; iq <= q; iq++) {
string pref, suf;
cin >> pref >> suf;
reverse(suf.begin(), suf.end());
auto xx = getInterval(root1, pref);
auto yy = getInterval(root2, suf);
if (xx.first > xx.second || yy.first > yy.second) {
continue;
}
int xmin = xx.first, xmax = xx.second;
int ymin = yy.first, ymax = yy.second;
bboxes.push_back({xmin, ymin, xmax, ymax, iq});
}
/// sort(bboxes.begin(), bboxes.end());
for (auto &bbox : bboxes) {
int xmin = bbox.xmin, ymin = bbox.ymin;
int xmax = bbox.xmax, ymax = bbox.ymax;
int sol = 0;
for (int i = 1; i <= n; i++) {
sol += (xmin <= x[i] && x[i] <= xmax && ymin <= y[i] && y[i] <= ymax);
}
solPrint[bbox.index] = sol;
}
for (int iq = 1; iq <= q; iq++) {
cout << solPrint[iq] << "\n";
}
return 0;
}
