#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using RNA = vector<int>;
const int MAXN = 100'001;
struct Trie {
static constexpr int N = 4;
struct TrieNode {
TrieNode *next[N];
int st = MAXN;
int en = -1;
};
TrieNode *root;
Trie() {
root = new TrieNode();
}
void add_string(const RNA &s, int index) {
TrieNode *curr = root;
for (int c : s) {
if (!curr->next[c]) {
curr->next[c] = new TrieNode();
}
curr = curr->next[c];
curr->st = min(curr->st, index);
curr->en = max(curr->en, index);
}
}
pair<int, int> get_bounds(const RNA &s) const {
TrieNode *curr = root;
for (int c : s) {
if (!curr->next[c]) {
return {-1, -1};
}
curr = curr->next[c];
}
return {curr->st, curr->en};
}
};
struct PersistentTrie {
static constexpr int N = 4;
struct PersistentTrieNode {
PersistentTrieNode *next[N];
int cnt = 0;
PersistentTrieNode *get_copy() {
PersistentTrieNode *res = new PersistentTrieNode();
res->cnt = cnt;
for (int i = 0; i < N; i++) {
res->next[i] = next[i];
}
return res;
}
};
vector<PersistentTrieNode*> roots;
PersistentTrie() {
roots.emplace_back(new PersistentTrieNode());
}
void add_string(const RNA &s) {
roots.emplace_back(roots.back()->get_copy());
PersistentTrieNode *curr = roots.back();
for (int i = s.size() - 1; i >= 0; i--) {
if (curr->next[s[i]]) {
curr->next[s[i]] = curr->next[s[i]]->get_copy();
} else {
curr->next[s[i]] = new PersistentTrieNode();
}
curr = curr->next[s[i]];
curr->cnt++;
}
}
int get_count(const RNA &s, int time) {
if (time < 0) return 0;
PersistentTrieNode *curr = roots[time];
for (int i = s.size() - 1; i >= 0; i--) {
if (!curr->next[s[i]]) {
return 0;
}
curr = curr->next[s[i]];
}
return curr->cnt;
}
};
RNA string_to_rna(const string &s) {
RNA res;
for (char c : s) {
if (c == 'A') {
res.emplace_back(0);
} else if (c == 'G') {
res.emplace_back(1);
} else if (c == 'C') {
res.emplace_back(2);
} else if (c == 'U') {
res.emplace_back(3);
}
}
return res;
}
void solve() {
int n, q; cin >> n >> q;
vector<RNA> v(n+1);
for (int i = 1; i <= n; i++) {
string s; cin >> s;
v[i] = string_to_rna(s);
}
sort(v.begin(), v.end());
Trie trie;
PersistentTrie ptrie;
for (int i = 1; i <= n; i++) {
trie.add_string(v[i], i);
ptrie.add_string(v[i]);
}
while (q--) {
string as, bs; cin >> as >> bs;
RNA a = string_to_rna(as);
RNA b = string_to_rna(bs);
auto [l, r] = trie.get_bounds(a);
int ans = ptrie.get_count(b, r) - ptrie.get_count(b, l-1);
cout << ans << "\n";
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
solve();
return 0;
}
