#ifdef LOCAL
#include "/home/bgopc/template/pch.hpp"
#endif
#include <bits/stdc++.h>
using namespace std;
// * No One Dies a Virgin, Life Fucks Us All
typedef long long ll;
#define nl '\n'
#define ff first
#define ss second
#define pb push_back
#define sik(x) {cout << x << nl; return;}
constexpr ll maxn = 2e6+10, mod = 1e9 + 7, inf = 1e17, SQ = 450, LG = 20, K = 26;
typedef pair<int, int> pii;
struct Trie {
int ch[maxn][K], in[maxn], out[maxn], T;
int TSZ = 0;
void init() {
for (int i = 0 ; i <= TSZ ; i ++) fill(ch[i], ch[i] + K, 0), in[i] = out[i] = 0;
TSZ = 0;
T = 1;
}
inline void add(const string& s) {
int v = 0;
//cerr << "Adding " << s << nl;
for (char c : s) {
int u = c - 'A';
if (!ch[v][u]) ch[v][u] = ++ TSZ;
v = ch[v][u];
}
//cerr << "Add ed
}
void dfs(int v, int p = -1) {
in[v] = T ++;
for (int i = 0 ; i < K ; i ++) {
if (ch[v][i]) dfs(ch[v][i], v);
}
out[v] = T;
}
int get(const string& s) {
int v = 0;
for (char c : s) {
int u = c - 'A';
if (!ch[v][u]) return -1;
v = ch[v][u];
}
return v;
}
};
struct Fenwick {
int fen[maxn];
void init() {
memset(fen, 0, sizeof fen);
}
inline void add(int p, int x = 1) {
for (++ p ; p < maxn ; p += p & -p) fen[p] += x;
}
inline int get(int p) {
int res = 0;
for (++ p ; p ; p -= p & -p) res += fen[p];
return res;
}
};
int n, q, ans[maxn];
string s[maxn], rs[maxn];
Trie T, RT;
vector<array<int, 3>> Q[maxn];
vector<int> Add[maxn];
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
T.init();
RT.init();
for (int i = 1 ; i <= n ; i ++) {
cin >> s[i];
rs[i] = s[i];
reverse(rs[i].begin(), rs[i].end());
T.add(s[i]);
RT.add(rs[i]);
}
//cerr << "Done1\n";
T.dfs(0);
RT.dfs(0);
//cerr << "Done 2\n";
for (int i = 1 ; i <= q ; i ++) {
string A, B;
cin >> A >> B;
reverse(B.begin(), B.end());
int v = T.get(A), u = RT.get(B);
if (v == -1 || u == -1) {
//cerr << "Skipped " << i << ' ' << v << ' ' << u << nl;;
continue;
}
// T.in[v] <= ... <= T.out[v]
int x1 = T.in[v], y1 = T.out[v] - 1, x2 = RT.in[u], y2 = RT.out[u] - 1;
// F(y1, y2) - F(y1, x2) - F(x1, y2) + F(x1, x2)
Q[x1 - 1].pb({x2 - 1, i, +1});
Q[x1 - 1].pb({y2, i, -1});
Q[y1].pb({x2 - 1, i, -1});
Q[y1].pb({y2, i, +1});
}
for (int i = 1 ; i <= n ; i ++) {
int v = T.get(s[i]), u = RT.get(rs[i]);
Add[T.in[v]].pb(RT.in[u]);
}
Fenwick fen;
fen.init();
for (int i = 0 ; i < maxn ; i ++) {
for (int x : Add[i]) {
fen.add(x);
}
for (auto [p, id, x] : Q[i]) {
ans[id] += x * fen.get(p);
}
}
for (int i = 1 ; i <= q ; i ++) cout << ans[i] << nl;
}
