#include <bits/stdc++.h>
using namespace std;
template <typename T>
class fenwick {
public:
vector<T> fenw;
int n;
fenwick(int _n) : n(_n) {
fenw.resize(n);
}
void modify(int x, T v) {
while (x < n) {
fenw[x] += v;
x |= (x + 1);
}
}
T get(int x) {
T v{};
while (x >= 0) {
v += fenw[x];
x = (x & (x + 1)) - 1;
}
return v;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<string> s(n);
for (int i = 0; i < n; i++) {
cin >> s[i];
}
vector<string> L(m), R(m);
for (int i = 0; i < m; i++) {
cin >> L[i] >> R[i];
}
vector<vector<int>> trie(1, vector<int>(26, -1));
for (int i = 0; i < n; i++) {
int t = 0;
for (int j = 0; j < (int) s[i].size(); j++) {
int c = (int) (s[i][j] - 'A');
if (trie[t][c] == -1) {
trie[t][c] = trie.size();
trie.emplace_back(vector<int>(26, -1));
}
t = trie[t][c];
}
}
for (int i = 0; i < m; i++) {
int t = 0;
for (int j = 0; j < (int) L[i].size(); j++) {
int c = (int) (L[i][j] - 'A');
if (trie[t][c] == -1) {
trie[t][c] = trie.size();
trie.emplace_back(vector<int>(26, -1));
}
t = trie[t][c];
}
}
int k = trie.size();
vector<int> tl(k), tr(k);
int T;
function<void(int)> Dfs = [&](int u) {
tl[u] = ++T;
for (int i = 0; i < 26; i++) {
if (trie[u][i] != -1) {
Dfs(trie[u][i]);
}
}
tr[u] = T;
};
T = 0;
Dfs(0);
vector<int> x(n);
vector<int> xl(m), xr(m);
for (int i = 0; i < n; i++) {
int t = 0;
for (int j = 0; j < (int) s[i].size(); j++) {
int c = (int) (s[i][j] - 'A');
t = trie[t][c];
}
x[i] = tl[t];
}
for (int i = 0; i < m; i++) {
int t = 0;
for (int j = 0; j < (int) L[i].size(); j++) {
int c = (int) (L[i][j] - 'A');
t = trie[t][c];
}
xl[i] = tl[t];
xr[i] = tr[t];
}
trie.clear();
trie.emplace_back(vector<int>(26, -1));
for (int i = 0; i < n; i++) {
reverse(s[i].begin(), s[i].end());
int t = 0;
for (int j = 0; j < (int) s[i].size(); j++) {
int c = (int) (s[i][j] - 'A');
if (trie[t][c] == -1) {
trie[t][c] = trie.size();
trie.emplace_back(vector<int>(26, -1));
}
t = trie[t][c];
}
}
for (int i = 0; i < m; i++) {
reverse(R[i].begin(), R[i].end());
int t = 0;
for (int j = 0; j < (int) R[i].size(); j++) {
int c = (int) (R[i][j] - 'A');
if (trie[t][c] == -1) {
trie[t][c] = trie.size();
trie.emplace_back(vector<int>(26, -1));
}
t = trie[t][c];
}
}
k = trie.size();
tl.resize(k);
tr.resize(k);
T = 0;
Dfs(0);
vector<int> y(n);
vector<int> yl(m), yr(m);
for (int i = 0; i < n; i++) {
int t = 0;
for (int j = 0; j < (int) s[i].size(); j++) {
int c = (int) (s[i][j] - 'A');
t = trie[t][c];
}
y[i] = tl[t];
}
for (int i = 0; i < m; i++) {
int t = 0;
for (int j = 0; j < (int) R[i].size(); j++) {
int c = (int) (R[i][j] - 'A');
t = trie[t][c];
}
yl[i] = tl[t];
yr[i] = tr[t];
}
const int MAX = (int) 2e6 + 5;
vector<vector<vector<int>>> qs(MAX, vector<vector<int>>(3));
for (int i = 0; i < n; i++) {
qs[x[i]][1].push_back(i);
}
for (int i = 0; i < m; i++) {
qs[xl[i]][0].push_back(i);
qs[xr[i]][2].push_back(i);
}
vector<int> ans(m);
fenwick<int> fenw(MAX);
for (int i = 0; i < MAX; i++) {
for (int j : qs[i][0]) {
ans[j] -= fenw.get(yr[j]) - fenw.get(yl[j] - 1);
}
for (int j : qs[i][1]) {
fenw.modify(y[j], 1);
}
for (int j : qs[i][2]) {
ans[j] += fenw.get(yr[j]) - fenw.get(yl[j] - 1);
}
}
for (int i = 0; i < m; i++) {
cout << ans[i] << '\n';
}
return 0;
}
