#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
const int INF = 2000000000;
struct Node {
int child[4];
vector<int> ids;
int l, r;
Node() {
memset(child, -1, sizeof(child));
ids.clear();
l = INF; r = 0;
}
};
struct Trie {
vector<Node> node;
Trie() { node.emplace_back(); } // root = 0
int new_node() {
node.emplace_back();
return (int)node.size() - 1;
}
void add(const string &s, int id, int type) {
// update root to support empty query
if (type == 2) node[0].ids.push_back(id);
else { node[0].l = min(node[0].l, id); node[0].r = max(node[0].r, id); }
int p = 0;
for (char ch : s) {
int x = ch - '0';
if (x < 0 || x > 3) return; // defensive
if (node[p].child[x] == -1) node[p].child[x] = new_node();
p = node[p].child[x];
if (type == 2) node[p].ids.push_back(id);
else { node[p].l = min(node[p].l, id); node[p].r = max(node[p].r, id); }
}
}
pii get_range(const string &s) {
int p = 0;
for (char ch : s) {
int x = ch - '0';
if (x < 0 || x > 3) return {-1,-1};
int nxt = node[p].child[x];
if (nxt == -1) return {-1,-1};
p = nxt;
}
if (node[p].l > node[p].r) return {-1,-1};
return {node[p].l, node[p].r};
}
vector<int> get_ids(const string &s) {
int p = 0;
for (char ch : s) {
int x = ch - '0';
if (x < 0 || x > 3) return {};
int nxt = node[p].child[x];
if (nxt == -1) return {};
p = nxt;
}
return node[p].ids;
}
};
void compress_string(string &s) {
for (char &c : s) {
if (c=='A' || c=='a') c='0';
else if (c=='G' || c=='g') c='1';
else if (c=='U' || c=='u') c='2';
else if (c=='C' || c=='c') c='3';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
if (!(cin >> n >> q)) return 0;
vector<string> orig(n+1);
for (int i = 1; i <= n; ++i) cin >> orig[i];
vector<pair<string,int>> arr;
arr.reserve(n);
for (int i = 1; i <= n; ++i) {
string t = orig[i];
compress_string(t);
arr.emplace_back(t, i);
}
sort(arr.begin(), arr.end(), [](const pair<string,int>& a, const pair<string,int>& b){
return a.first < b.first;
});
vector<string> s_sorted(n+1);
vector<int> pos(n+1);
for (int i = 0; i < n; ++i) {
s_sorted[i+1] = arr[i].first;
pos[arr[i].second] = i+1;
}
Trie pre, suf;
for (int i = 1; i <= n; ++i) {
pre.add(s_sorted[i], i, 1);
}
for (int orig_idx = 1; orig_idx <= n; ++orig_idx) {
string t = arr[ pos[orig_idx] - 1 ].first;
}
for (int i = 1; i <= n; ++i) {
string t = orig[i];
compress_string(t);
reverse(t.begin(), t.end());
suf.add(t, pos[i], 2);
}
for (auto &nd : suf.node) {
if (!nd.ids.empty()) sort(nd.ids.begin(), nd.ids.end());
}
while (q--) {
string P, Q;
cin >> P >> Q;
compress_string(P);
compress_string(Q);
pii range = pre.get_range(P);
if (range.first == -1) { cout << 0 << '\n'; continue; }
reverse(Q.begin(), Q.end());
vector<int> vec = suf.get_ids(Q);
if (vec.empty()) { cout << 0 << '\n'; continue; }
int L = lower_bound(vec.begin(), vec.end(), range.first) - vec.begin();
int R = upper_bound(vec.begin(), vec.end(), range.second) - vec.begin();
cout << (R - L) << '\n';
}
return 0;
}
