#include <bits/stdc++.h>
using namespace std;
namespace std {
#ifndef LOCAL
#define cerr \
if (0) cerr
#endif
} // namespace std
char mp[256];
struct TrieNode {
int cnt;
int child[4];
TrieNode() {
cnt = 0;
memset(child, 0, sizeof(child));
}
};
struct Trie {
TrieNode trie[2000005];
int tin[2000005];
int tout[2000005];
int timeDFS = 0;
int numNode = 0;
Trie() {}
void add(string s) {
int u = 0;
for (char c : s) {
c = mp[c];
if (trie[u].child[c] == 0) {
trie[u].child[c] = ++numNode;
}
u = trie[u].child[c];
}
trie[u].cnt++;
}
void dfs(int u) {
tin[u] = ++timeDFS;
for (int i = 0; i < 4; i++) {
if (trie[u].child[i]) {
dfs(trie[u].child[i]);
}
}
tout[u] = timeDFS;
}
};
struct Fen {
int ft[2000005];
Fen() { memset(ft, 0, sizeof(ft)); }
void add(int x, int delta) {
for (; x <= 2e6; x += x & -x) ft[x] += delta;
}
int get(int x) {
int ans = 0;
for (; x > 0; x -= x & -x) ans += ft[x];
return ans;
}
};
Trie pref, suff;
int node_pref[100005];
int node_suff[100005];
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifdef LOCAL
#define task ""
#else
#define task "RNA"
#endif
if (fopen(task ".inp", "r")) {
freopen(task ".inp", "r", stdin);
freopen(task ".out", "w", stdout);
}
mp['G'] = 0;
mp['U'] = 1;
mp['A'] = 2;
mp['C'] = 3;
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
pref.add(s);
{
int u = 0;
for (char c : s) {
c = mp[c];
u = pref.trie[u].child[c];
}
node_pref[i] = u;
}
reverse(s.begin(), s.end());
suff.add(s);
{
int u = 0;
for (char c : s) {
c = mp[c];
u = suff.trie[u].child[c];
}
node_suff[i] = u;
}
}
pref.dfs(0);
suff.dfs(0);
vector<array<int, 5>> que;
vector<int> ans(m);
for (int i = 0; i < m; i++) {
string pre, suf;
cin >> pre >> suf;
[&]() {
int pref_node = 0;
for (char& c : pre) {
c = mp[c];
pref_node = pref.trie[pref_node].child[c];
if (!pref_node) {
return;
}
}
reverse(suf.begin(), suf.end());
int suf_node = 0;
for (char& c : suf) {
c = mp[c];
suf_node = suff.trie[suf_node].child[c];
if (!suf_node) {
return;
}
}
// tin[pref_node] <= tin[node_pref[i]] <= tout[pref_node]
// tin[suff_node] <= tin[node_suff[i]] <= tout[suff_node]
que.push_back({pref.tin[pref_node] - 1, -1, suff.tin[suf_node], suff.tout[suf_node], i});
que.push_back({pref.tout[pref_node], 1, suff.tin[suf_node], suff.tout[suf_node], i});
}();
}
for (int i = 1; i <= n; i++) {
que.push_back({pref.tin[node_pref[i]], -2, suff.tin[node_suff[i]], -1, -1});
}
sort(que.begin(), que.end());
Fen fen;
for (auto [_, delta, l, r, i] : que) {
if (delta == -2) {
fen.add(l, 1);
} else {
ans[i] += delta * (fen.get(r) - fen.get(l - 1));
}
}
for (auto it : ans) cout << it << '\n';
return 0;
}
