#include <bits/stdc++.h>
using namespace std;
#define loop(i, a, b) for(int i = a; i <= b; i++)
#define loop_rev(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define pb push_back
using ll = long long;
struct TreeNode {
int l = 0, r = 0, sum = 0;
};
const int TREE_BASE = (1 << 18);
const int MAX_N = 100'000;
TreeNode st_pool[MAX_N * 18 + 1'000];
int st_node() {
static int node_id = 0;
return ++node_id;
}
struct SegTree {
int root = 0;
void update(int i, int val, int& v, int l, int r) {
if(v == 0) v = st_node();
st_pool[v].sum += val;
if(l != r) {
int mid = (l + r) / 2;
if(i <= mid) update(i, val, st_pool[v].l, l, mid);
else update(i, val, st_pool[v].r, mid + 1, r);
}
}
void update(int i, int val) {
update(i, val, root, 0, TREE_BASE - 1);
}
int query(int a, int b, int v, int l, int r) {
if(v == 0) return 0;
if(l >= a && r <= b) {
return st_pool[v].sum;
}
int mid = (l + r) / 2, res = 0;
if(a <= mid) {
res += query(a, b, st_pool[v].l, l, mid); // BUG FOUND: Quadratic query (l <= mid instead of a <= mid)
}
if(b > mid) {
res += query(a, b, st_pool[v].r, mid + 1, r);
}
return res;
}
int query(int a, int b) {
return query(a, b, root, 0, TREE_BASE - 1);
}
void include(int &v_this, int v_other) {
if(v_other == 0) return;
if(v_this == 0) { v_this = v_other; return; }
if(st_pool[v_other].l)
include(st_pool[v_this].l, st_pool[v_other].l);
if(st_pool[v_other].r)
include(st_pool[v_this].r, st_pool[v_other].r);
st_pool[v_this].sum = st_pool[st_pool[v_this].l].sum + st_pool[st_pool[v_this].r].sum;
}
void include_disjoint_segtree(SegTree& other) {
include(root, other.root);
}
};
struct TrieNode {
int ptr[4];
vector<int> values;
int tin = 0, tout = 0;
SegTree st;
};
const int MAX_LEN = 2'000'000;
TrieNode trie_pool[2 * MAX_LEN + 1'000];
int trie_node() {
static int node_id = 0;
return ++node_id;
}
struct Trie {
int root = trie_node();
int insert(string const& s, int value) {
int v = root;
loop(i, 0, sz(s) - 1) {
int& dest = trie_pool[v].ptr[s[i] - 'a'];
if(!dest) dest = trie_node();
v = dest;
}
trie_pool[v].values.pb(value);
return v;
}
int find(string const& s) {
int v = root;
loop(i, 0, sz(s) - 1) {
if(!v) return 0;
int& dest = trie_pool[v].ptr[s[i] - 'a'];
v = dest;
}
return v;
}
void euler_tour() {
int timer = 1;
_euler_tour(root, timer);
}
void _euler_tour(int v, int& timer) {
int cnt = 0; for(int s : trie_pool[v].ptr) cnt += (s != 0);
trie_pool[v].tin = timer;
for(int s : trie_pool[v].ptr) {
if(!s) continue;
if(sz(trie_pool[v].values) || cnt > 1) ++timer;
_euler_tour(s, timer);
}
trie_pool[v].tout = timer;
}
vector<int> rev_topo() {
vector<int> res; _rev_topo(root, res); return res;
}
void _rev_topo(int v, vector<int>& res) {
for(int s : trie_pool[v].ptr) {
if(s) _rev_topo(s, res);
}
res.pb(v);
}
};
void F(string& s) { for(char& c : s) if(c == 'A') c = 'a'; else if(c == 'G') c = 'b'; else if(c == 'C') c = 'c'; else if(c == 'U') c = 'd'; }
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, m; cin >> n >> m;
vector<int> trie_id(n + 1);
vector<string> S(n + 1);
Trie pref, suff;
loop(i, 1, n) {
cin >> S[i]; F(S[i]);
trie_id[i] = pref.insert(S[i], i);
}
pref.euler_tour();
loop(i, 1, n) {
reverse(all(S[i]));
suff.insert(S[i], i);
}
vector<int> res(m + 1);
vector<int> id_p(m + 1);
auto order = suff.rev_topo();
loop(i, 1, m) {
string p, q; cin >> p >> q; F(p), F(q);
id_p[i] = pref.find(p);
reverse(all(q)); int id_q = suff.find(q);
if(id_q != 0) {
trie_pool[id_q].values.pb(-i);
}
}
for(int v : order) {
for(int s : trie_pool[v].ptr) {
if(s) trie_pool[v].st.include_disjoint_segtree(trie_pool[s].st);
}
for(int val : trie_pool[v].values) {
if(val > 0) {
trie_pool[v].st.update(trie_pool[trie_id[val]].tin, 1);
}
else {
int q_ind = (-val), pref_id = id_p[q_ind];
if(pref_id != 0) res[q_ind] = trie_pool[v].st.query(trie_pool[pref_id].tin, trie_pool[pref_id].tout);
}
}
}
loop(i, 1, m) {
cout << res[i] << '\n';
}
}
