#include <bits/stdc++.h>
using namespace std;
int idx(char c) {
if (c == 'A') return 0;
if (c == 'C') return 1;
if (c == 'G') return 2;
return 3; // 'U'
}
struct Trie {
vector<array<int,4>> Tree;
vector<vector<int>> sf;
Trie() {
Tree.reserve(4);
sf.reserve(4);
Tree.push_back({-1,-1,-1,-1});
sf.push_back(vector<int>());
}
void reserve_nodes(size_t expect) {
Tree.reserve(expect);
sf.reserve(expect);
}
void clear() {
Tree.clear();
sf.clear();
Tree.push_back({-1,-1,-1,-1});
sf.push_back(vector<int>());
}
void Insert(const string &s, int id) {
int node = 0;
for (char c : s) {
int x = idx(c);
if (Tree[node][x] == -1) {
Tree[node][x] = (int)Tree.size();
Tree.push_back({-1,-1,-1,-1});
sf.push_back(vector<int>());
}
node = Tree[node][x];
sf[node].push_back(id);
}
}
int FindNode(const string &s) const {
int node = 0;
for (char c : s) {
int x = idx(c);
if (Tree[node][x] == -1) return -1;
node = Tree[node][x];
}
return node;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
if (!(cin >> n >> m)) return 0;
vector<string> a(n+1);
long long sumLen = 0;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
sumLen += (int)a[i].size();
}
Trie p, q;
p.reserve_nodes((size_t)min<long long>(sumLen + 5, (long long)2e6));
q.reserve_nodes((size_t)min<long long>(sumLen + 5, (long long)2e6));
for (int i = 1; i <= n; ++i) p.Insert(a[i], i);
vector<string> L(m+1), R(m+1);
vector<int> pid(m+1, -1), qid(m+1, -1);
for (int i = 1; i <= m; ++i) {
cin >> L[i] >> R[i];
pid[i] = p.FindNode(L[i]);
}
for (int i = 1; i <= n; ++i) {
string rs = a[i];
reverse(rs.begin(), rs.end());
q.Insert(rs, i);
}
unordered_map<long long,int> cache;
cache.reserve(m * 2);
for (int i = 1; i <= m; ++i) {
if (pid[i] == -1) {
cout << 0 << '\n';
continue;
}
string rr = R[i];
reverse(rr.begin(), rr.end());
int qnode = q.FindNode(rr);
qid[i] = qnode;
if (qnode == -1) {
cout << 0 << '\n';
continue;
}
long long key = ( (long long)pid[i] << 32 ) ^ (unsigned long long)qnode;
auto it = cache.find(key);
if (it != cache.end()) {
cout << it->second << '\n';
continue;
}
const vector<int> &A = p.sf[pid[i]];
const vector<int> &B = q.sf[qnode];
// Nếu một trong hai rỗng thì 0
if (A.empty() || B.empty()) {
cache[key] = 0;
cout << 0 << '\n';
continue;
}
const vector<int> *small = &A, *large = &B;
if (A.size() > B.size()) swap(small, large);
int cnt = 0;
for (int v : *small) {
if (binary_search(large->begin(), large->end(), v)) ++cnt;
}
cache[key] = cnt;
cout << cnt << '\n';
}
return 0;
}
