#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const char nl = '\n';
template<class T>
struct offline_fenwick2d {
int n;
vector<vector<T>> vals, bit;
T f(T a, T b) {
return (a + b);
}
// upd stores updates in form of [x, y]
offline_fenwick2d(int n, vector<pair<T, T>> &upd) : n(n), vals(n + 1), bit(n + 1) {
sort(begin(upd), end(upd), [&](const pair<T, T> &p1, const pair<T, T> &p2) {
return p1.second < p2.second;
});
for (int i = 1; i <= n; i++) {
vals[i].push_back(0), bit[i].push_back(0);
}
for (const auto &[x, y]: upd) {
for (int i = x; i <= n; i += i & -i) {
if (y != vals[i].back()) {
vals[i].push_back(y), bit[i].push_back(0);
}
}
}
}
// largest idx i such that vals[x][i] <= y
int idx(int x, int y) {
return upper_bound(begin(vals[x]), end(vals[x]), y) - begin(vals[x]) - 1;
}
void update(int x, int y, T v) {
for (; x <= n; x += x & -x) {
// vals[x][idx(x, y)] must be exactly y as we built the array based on the updates beforehand
for (int z = idx(x, y); z < bit[x].size(); z += z & -z) {
bit[x][z] = f(bit[x][z], v);
}
}
}
// returns rectangular query from (1, 1) to (x, y)
T query(int x, int y) {
T ans = 0;
for (; x >= 1; x -= x & -x) {
for (int z = idx(x, y); z >= 1; z -= z & -z) {
ans = f(ans, bit[x][z]);
}
}
return ans;
}
int query(int x1, int y1, int x2, int y2) {
return query(x2, y2) - query(x2, y1 - 1) - query(x1 - 1, y2) + query(x1 - 1, y1 - 1);
}
};
struct trie {
vector<array<int, 26>> tr;
vector<int> tin, tout;
trie() {
tr.assign(1, {});
}
int insert(string &s, char shft = 'A') {
int u = 0;
for (auto &c: s) {
if (!tr[u][c - shft]) {
tr[u][c - shft] = tr.size();
tr.emplace_back();
}
u = tr[u][c - shft];
}
return u;
}
void build() {
tin.assign(tr.size(), 0);
tout.assign(tr.size(), 0);
int ctime = 0;
auto dfs = [&](auto &&dfs, int u) -> void {
tin[u] = ++ctime;
for (int i = 0; i < 26; i++) {
int v = tr[u][i];
if (!v) continue;
dfs(dfs, v);
}
tout[u] = ctime;
};
dfs(dfs, 0);
}
pair<int, int> range(int u) {
return {tin[u], tout[u]};
}
};
void solve() {
int n, q;
cin >> n >> q;
vector<pair<int, int>> upds(n);
trie pre, suf;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
int u = pre.insert(s);
upds[i].first = u;
reverse(all(s));
u = suf.insert(s);
upds[i].second = u;
}
vector<pair<int, int>> qpre(q), qsuf(q);
for (int i = 0; i < q; i++) {
string p, s;
cin >> p >> s;
int u = pre.insert(p);
qpre[i].first = u;
reverse(all(s));
u = suf.insert(s);
qsuf[i].first = u;
}
pre.build();
suf.build();
for (auto &[u, v]: upds) {
u = pre.range(u).first;
v = suf.range(v).first;
}
for (int i = 0; i < q; i++) {
qpre[i] = pre.range(qpre[i].first);
qsuf[i] = suf.range(qsuf[i].first);
}
int mx = max(pre.tout[0], suf.tout[0]) + 5;
offline_fenwick2d<int> tree(mx, upds);
for (auto &[x, y]: upds) tree.update(x, y, 1);
for (int i = 0; i < q; i++) {
auto [x1, x2] = qpre[i];
auto [y1, y2] = qsuf[i];
cout << tree.query(x1, y1, x2, y2) << nl;
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifndef ONLINE_JUDGE
freopen("../in.txt", "r", stdin);
freopen("../out.txt", "w", stdout);
#endif
solve();
}
