#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
const int N = 1e5 + 5, MAX = 2e6 + 5, C = 26;
struct Trie {
int tot = 1;
int nxt[MAX][C], ord[MAX], tout[MAX];
int add(int p, char c) {
if (!nxt[p][c - 'A']) {
nxt[p][c - 'A'] = ++tot;
}
return nxt[p][c - 'A'];
}
void ins(const string &s) {
int p = 1;
for (char c : s) {
p = add(p, c);
}
}
int timer = 0;
void dfs(int u) {
ord[u] = ++timer;
for (int i = 0; i < C; ++i) {
if (nxt[u][i]) {
dfs(nxt[u][i]);
}
}
tout[u] = timer;
}
int search(const string &s) {
int p = 1;
for (char c : s) {
if (!nxt[p][c - 'A']) {
return 0;
}
p = nxt[p][c - 'A'];
}
return p;
}
} pf, sf;
int n, m;
int ft[MAX], res[N];
string s[N];
void upd(int i, int x) {
for (; i < MAX; i += i & -i) {
ft[i] += x;
}
}
int qry(int i) {
int res = 0;
for (; i; i -= i & -i) {
res += ft[i];
}
return res;
}
int qry(int l, int r) {
return qry(r) - qry(l - 1);
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> s[i];
pf.ins(s[i]);
reverse(s[i].begin(), s[i].end());
sf.ins(s[i]);
}
pf.dfs(1);
sf.dfs(1);
vector<array<int, 2>> pt;
for (int i = 1; i <= n; ++i) {
int y = sf.search(s[i]);
reverse(s[i].begin(), s[i].end());
int x = pf.search(s[i]);
pt.push_back({pf.ord[x], sf.ord[y]});
}
vector<array<int, 4>> Queries;
for (int i = 1; i <= m; ++i) {
string P, Q; cin >> P >> Q;
reverse(Q.begin(), Q.end());
int p = pf.search(P), q = sf.search(Q);
if (p && q) {
int x = pf.ord[p], y = pf.tout[p], a = sf.ord[q], b = sf.tout[q];
Queries.push_back({x - 1, a, b, -i});
Queries.push_back({y, a, b, i});
}
}
sort(Queries.begin(), Queries.end());
sort(pt.begin(), pt.end());
int j = 0;
for (auto [x, u, v, id] : Queries) {
while (j < pt.size() && pt[j][0] <= x) {
upd(pt[j][1], 1);
++j;
}
if (id > 0) {
res[id] += qry(u, v);
} else {
res[-id] -= qry(u, v);
}
}
for (int i = 1; i <= m; ++i) {
cout << res[i] << "\n";
}
return 0;
}
