套路题，来讲个套路解法。
如果没有后缀的要求，答案就是 trie 树的子树内字符串数量。现在加上了后缀，尝试继续使用 trie 树解决问题。
我们建立两棵 trie 树 \(T_1,T_2\)，其中 \(T_1\) 是正常的 trie 树，\(T_2\) 是每个字符串翻转后的 trie 树。这样的话，包含给定后缀的字符串在 \(T_2\) 上构成一棵子树。例如，样例一中的两棵 trie 树如下：
考虑一个询问意味着什么，其实就是查询同时在 \(T_1\) 一棵子树和 \(T_2\) 一棵子树内的字符串数。例如 \((\texttt{AU},\texttt{C})\) 就是查询同时在 \(T_1\) 的节点 \(2\) 的子树和 \(T_2\) 的节点 \(1\) 的子树内的字符串数，只有 \(\texttt{AUGC}\) 符合要求，因此答案为 \(1\)。
把每个字符串抽象为坐标 \((x,y)\) 的点，其中 \(x,y\) 分别是 \(T_1,T_2\) 上字符串终止节点的 dfs 序，那么一次询问就是查询一个矩形内部点的数量，是二维数点问题，扫描线维护即可。
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
uniform_int_distribution<int> dist(L, R);
return dist(rnd);
}
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
const int N = 2e6+5;
int n, m, ans[N];
string s, t;
vector<tuple<int, int>> dots;
vector<tuple<int, int, int, int>> queries;
int f(char c) {
if(c == 'A') return 0;
if(c == 'G') return 1;
if(c == 'U') return 2;
if(c == 'C') return 3;
return -1;
}
struct Trie {
int son[N][4], tot, sz[N], dfn[N], tms;
int insert(string s) {
int u = 0;
for(char c : s) {
int k = f(c);
if(!son[u][k]) son[u][k] = ++tot;
u = son[u][k];
}
return u;
}
int find(string s) {
int u = 0;
for(char c : s) {
int k = f(c);
if(!son[u][k]) return -1;
u = son[u][k];
}
return u;
}
void dfs(int u) {
dfn[u] = tms++;
sz[u] = 1;
rep(i, 0, 3) {
if(son[u][i]) {
dfs(son[u][i]);
sz[u] += sz[son[u][i]];
}
}
}
}pre, suf;
struct BIT {
int c[N];
int lowbit(int x) {return x & (-x);}
void add(int x, int k) {++x; for(; x < N; x += lowbit(x)) c[x] += k;}
int ask(int x) {++x; int k = 0; for(; x; x -= lowbit(x)) k += c[x]; return k;}
}bit;
int main() {
// freopen("debug.log", "w", stderr);
scanf("%d%d", &n, &m);
rep(i, 1, n) {
cin >> s;
int x = pre.insert(s);
reverse(s.begin(), s.end());
int y = suf.insert(s);
dots.emplace_back(x, y);
}
pre.tms = suf.tms = 0;
pre.dfs(0);
suf.dfs(0);
for(auto& [x, y] : dots) {
x = pre.dfn[x];
y = suf.dfn[y];
}
rep(i, 1, m) {
cin >> s >> t;
reverse(t.begin(), t.end());
int u = pre.find(s), v = suf.find(t);
if(u == -1 || v == -1) ans[i] = 0;
else {
// debug("# %d : %d %d %d %d\n", i, pre.dfn[u], suf.dfn[v], pre.dfn[u]+pre.sz[u]-1, suf.dfn[v]+suf.sz[v]-1);
queries.emplace_back(pre.dfn[u]-1, suf.dfn[v]-1, i, +1);
queries.emplace_back(pre.dfn[u]-1, suf.dfn[v]+suf.sz[v]-1, i, -1);
queries.emplace_back(pre.dfn[u]+pre.sz[u]-1, suf.dfn[v]-1, i, -1);
queries.emplace_back(pre.dfn[u]+pre.sz[u]-1, suf.dfn[v]+suf.sz[v]-1, i, +1);
}
}
sort(dots.begin(), dots.end());
sort(queries.begin(), queries.end());
// for(auto [x, y, id, mul] : queries) debug("* %d %d %d %d\n", x, y, id, mul);
int ds = (int)dots.size(), qs = (int)queries.size(), did = 0, qid = 0;
// debug("= %d %d\n", pre.tot, suf.tot);
rep(i, 0, pre.tot) {
// debug("? %d\n", i);
while(did < ds) {
auto [x, y] = dots[did];
if(x != i) break;
// debug("+ %d/%d : %d %d\n", did, ds, x, y);
bit.add(y, 1);
++did;
}
while(qid < qs) {
auto [x, y, id, mul] = queries[qid];
if(x != i) break;
// debug("! %d/%d : %d %d %d %d -> %d\n", qid, qs, x, y, id, mul, bit.ask(y));
ans[id] += mul * bit.ask(y);
++qid;
}
}
rep(i, 1, m) printf("%d\n", ans[i]);
return 0;
}