#include <bits/stdc++.h>
using namespace std;
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];
}
for (int i = 0; i < m; i++) {
int ans = 0;
for (int j = 0; j < n; j++) {
if (xl[i] <= x[j] && x[j] <= xr[i] && yl[i] <= y[j] && y[j] <= yr[i]) {
ans += 1;
}
}
cout << ans << '\n';
}
return 0;
}
