#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
int getNum(char c) {
if (c == 'A') return 1;
if (c == 'G') return 2;
if (c == 'C') return 3;
return 0;
}
int getChar(int n) {
if (n == 1) return 'A';
if (n == 2) return 'G';
if (n == 3) return 'C';
return 'U';
}
const int inf = 1e9;
struct Trie {
struct Node {
int l = inf;
int r = -inf;
int child[4];
Node () {
memset(child, 0, sizeof child);
}
};
int cur = 0;
Node node[2000005];
void Add(const string &s, int id) {
int u = 0;
for (char c : s) {
c = getNum(c);
if (node[u].child[c] == 0) node[u].child[c] = ++cur;
u = node[u].child[c];
node[u].l = min(node[u].l, id);
node[u].r = max(node[u].r, id);
}
}
pair<int, int> Range(const string &s) {
int u = 0;
for (char c : s) {
c = getNum(c);
if (node[u].child[c] == 0) node[u].child[c] = ++cur;
u = node[u].child[c];
}
return {node[u].l, node[u].r};
}
};
struct RverTrie {
struct Node {
vector<int> ids;
int child[4];
Node () {
memset(child, 0, sizeof child);
}
};
int cur = 0;
Node node[2000005];
void Add(const string &s, int id) {
int u = 0;
for (char c : s) {
c = getNum(c);
if (node[u].child[c] == 0) node[u].child[c] = ++cur;
u = node[u].child[c];
node[u].ids.push_back(id);
}
}
vector<int> getId(string &s) {
reverse(s.begin(), s.end());
int u = 0;
vector<int> tmp;
for (char c : s) {
c = getNum(c);
if (node[u].child[c] == 0) return tmp;
u = node[u].child[c];
}
return node[u].ids;
}
};
string a[200005];
int main () {
int n, m; cin >> n >> m;
for (int i = 0; i < n; i++) cin >> a[i];
sort(a, a+n);
Trie tri1;
RverTrie tri2;
for (int i = 0; i < n; i++) {
tri1.Add(a[i], i);
reverse(a[i].begin(), a[i].end());
tri2.Add(a[i], i);
}
while (m--) {
string p, q; cin >> p >> q;
auto rag = tri1.Range(p);
vector<int> v = tri2.getId(q);
if (v.size() == 0 || rag.first == inf || rag.second == -inf) cout << 0 << '\n';
else {
int l = lower_bound(v.begin(), v.end(), rag.first) - v.begin();
int r = upper_bound(v.begin(), v.end(), rag.second) - v.begin();
cout << r-l << '\n';
}
}
return 0;
}
