#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int NMAX = 1e5;
const int QMAX = 1e5;
struct Node {
Node* sons[4];
vector <int> wordList;
pair <int, int> wordRange;
Node() {
for(int i = 0; i < 4; i++) {
sons[i] = NULL;
}
}
};
int N, Q;
string s;
Node *pref = new Node, *suf = new Node;
int GetSon(char s) {
if(s == 'A') {
return 0;
} else if(s == 'G') {
return 1;
} else if(s == 'C') {
return 2;
}
return 3;
}
void InsertPref(Node* node, int index, int id) {
if(index == (int)s.size()) {
node-> wordList.push_back(id);
return;
}
int son = GetSon(s[index]);
if(node-> sons[son] == NULL) {
node-> sons[son] = new Node;
}
InsertPref(node-> sons[son], index + 1, id);
}
void InsertSuf(Node* node, int index, int id) {
if(index == -1) {
node-> wordList.push_back(id);
return;
}
int son = GetSon(s[index]);
if(node-> sons[son] == NULL) {
node-> sons[son] = new Node;
}
InsertSuf(node-> sons[son], index - 1, id);
}
string pr, sf;
vector<int> wordsWithPref, wordsWithSuf;
vector <int> prefOrder;
vector <int> sufOrder;
void DfsPref(Node* root) {
if(root == NULL) {
return ;
}
root->wordRange.first = (int)prefOrder.size() + 1;
for(int word : root-> wordList) {
prefOrder.push_back(word);
}
for(int j = 0; j < 4; j++) {
DfsPref(root-> sons[j]);
}
root->wordRange.second = (int)prefOrder.size();
}
void DfsSuf(Node* root) {
if(root == NULL) {
return ;
}
root->wordRange.first = (int)sufOrder.size() + 1;
for(int word : root-> wordList) {
sufOrder.push_back(word);
}
for(int j = 0; j < 4; j++) {
DfsSuf(root-> sons[j]);
}
root->wordRange.second = (int)sufOrder.size();
}
pair<int, int> GetRangePref(Node* root, int index) {
if(root == NULL) {
return {-1, -1};
}
if(index == (int)pr.size()) {
return root-> wordRange;
}
int son = GetSon(pr[index]);
return GetRangePref(root-> sons[son], index + 1);
}
pair<int, int> GetRangeSuf(Node* root, int index) {
if(root == NULL) {
return {-1, -1};
}
if(index == -1) {
return root-> wordRange;
}
int son = GetSon(sf[index]);
return GetRangeSuf(root-> sons[son], index - 1);
}
int posSuf[NMAX + 2], matchLine[NMAX + 2];
struct LineQuery {
int l, r, ind;
};
vector<LineQuery> lineQueries[NMAX + 2];
int k, ansLine[2 * QMAX + 2];
pair <int, int> qrl[QMAX + 2];
int ans[QMAX + 2];
int aib[NMAX + 2];
inline int LSB(int x) {
return x & (-x);
}
void Update(int pos) {
for(int i = pos; i <= N; i += LSB(i)) {
aib[i]++;
}
}
int Query(int pos) {
int ans = 0;
for(int i = pos; i > 0; i -= LSB(i)) {
ans += aib[i];
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> Q;
for(int i = 1; i <= N; i++) {
cin >> s;
InsertPref(pref, 0, i);
InsertSuf(suf, (int)s.size() - 1, i);
}
DfsPref(pref);
DfsSuf(suf);
for(int i = 1; i <= Q; i++) {
cin >> pr >> sf;
pair <int, int> rangePref = GetRangePref(pref, 0);
pair <int, int> rangeSuf = GetRangeSuf(suf, (int)sf.size() - 1);
if(rangePref.first == -1 || rangeSuf.first == -1 || (rangePref.first > rangePref.second) || (rangeSuf.first > rangeSuf.second)) {
ans[i] = 0;
} else {
++k;
lineQueries[rangePref.second].push_back({rangeSuf.first, rangeSuf.second, k});
++k;
lineQueries[rangePref.first - 1].push_back({rangeSuf.first, rangeSuf.second, k});
qrl[i] = {k - 1, k};
}
}
for(int i = 0; i < N; i++) {
posSuf[sufOrder[i]] = i + 1;
}
for(int i = 0; i < N; i++) {
matchLine[i + 1] = posSuf[prefOrder[i]];
}
for(int i = 1; i <= N; i++) {
Update(matchLine[i]);
for(LineQuery lq : lineQueries[i]) {
ansLine[lq.ind] = Query(lq.r) - Query(lq.l - 1);
}
}
for(int i = 1; i <= Q; i++) {
if(qrl[i].first != 0) {
ans[i] = ansLine[qrl[i].first] - ansLine[qrl[i].second];
}
}
for(int i = 1; i <= Q; i++) {
cout << ans[i] << '\n';
}
return 0;
}
