#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int L = 2000000 + 7;
const int N = (int) 1e5 + 7;
int aib[L];
void add(int i, int x) {
while (i < L) {
aib[i] += x;
i += i & -i;
}
}
int get(int i) {
int sol = 0;
while (i >= 1) {
sol += aib[i];
i -= i & -i;
}
return sol;
}
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;
};
struct Question {
int x;
int y;
int coef;
int index;
};
bool operator < (Question a, Question b) {
return a.x < b.x;
}
bool cmp(int i, int j) {
return x[i] < x[j];
}
int solPrint[N];
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
///freopen("input", "r", stdin);
int n, q;
cin >> n >> q;
vector<int> ord;
for (int i = 1; i <= n; i++) {
string s, revs;
ord.push_back(i);
cin >> s;
revs = s;
reverse(revs.begin(), revs.end());
addToTrie(root1, s, i);
addToTrie(root2, revs, i);
}
sort(ord.begin(), ord.end(), cmp);
prepTrie(root1, x);
prepTrie(root2, y);
vector<Question> questions;
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 x1 = xx.first, x2 = xx.second;
int y1 = yy.first, y2 = yy.second;
questions.push_back({x2, y2, +1, iq});
questions.push_back({x2, y1 - 1, -1, iq});
questions.push_back({x1 - 1, y2, -1, iq});
questions.push_back({x1 - 1, y1 - 1, +1, iq});
}
sort(questions.begin(), questions.end());
sort(ord.begin(), ord.end(), cmp);
int it = 0;
for (auto &question : questions) {
while (it < n && x[ord[it]] <= question.x) {
add(y[ord[it]], +1);
it++;
}
int sol = get(question.y);
sol *= question.coef;
solPrint[question.index] += sol;
}
for (int iq = 1; iq <= q; iq++) {
cout << solPrint[iq] << "\n";
}
return 0;
}
