#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
int n, m;
vector<pair<string, int>> s_pref, s_suf, pref, suf;
vector<vector<int>> ans;
bool compatible(const string& s1, const string& s2) {
if (s1.size() < s2.size()) return 0;
for (int i = 0; i < s2.size(); i++) {
if (s1[i] != s2[i]) return 0;
}
return 1;
}
int bs(int i, int l, bool cat) {
int r = n;
while (r - l > 1) {
int mid = (l + r) / 2;
if (cat) {
if (compatible(s_suf[mid].first, suf[i].first)) l = mid;
else r = mid - 1;
} else {
if (compatible(s_pref[mid].first, pref[i].first)) l = mid;
else r = mid - 1;
}
}
if (cat) {
if (compatible(s_suf[r].first, suf[i].first)) return r;
else if (compatible(s_suf[l].first, suf[i].first)) return l;
} else {
if (compatible(s_pref[r].first, pref[i].first)) return r;
else if (compatible(s_pref[l].first, pref[i].first)) return l;
}
return l - 1;
}
void solvePrefix() {
sort(s_pref.begin(), s_pref.end());
s_pref.push_back({"V", n});
sort(pref.begin(), pref.end());
int l = 0, r;
for (int i = 0; i < m; i++) {
while (s_pref[l].first <= pref[i].first and not compatible(s_pref[l].first, pref[i].first)) l++;
r = bs(i, l, 0);
// cout << pref[i].first << " : ";
if (n > 5000 or m > 5000) continue;
for (int j = l; j <= r; j++) {
// cout << s_pref[j].first << ' ';
ans[pref[i].second][s_pref[j].second]++;
}
// cout << '\n';
}
}
void solveSuffix() {
sort(s_suf.begin(), s_suf.end());
s_suf.push_back({"V", n});
sort(suf.begin(), suf.end());
int l = 0, r;
for (int i = 0; i < m; i++) {
while (s_suf[l].first <= suf[i].first and not compatible(s_suf[l].first, suf[i].first)) l++;
r = bs(i, l, 1);
// cout << suf[i].first << " : ";
if (n > 5000 or m > 5000) continue;
for (int j = l; j <= r; j++) {
// cout << s_suf[j].first << ' ';
ans[suf[i].second][s_suf[j].second]++;
}
// cout << '\n';
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
s_pref.resize(n), s_suf.resize(n), pref.resize(m), suf.resize(m);
if (n <= 5000 and m <= 5000) ans.resize(m, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
s_pref[i].second = s_suf[i].second = i;
string s;
cin >> s;
s_pref[i].first = s;
reverse(s.begin(), s.end());
s_suf[i].first = s;
}
for (int i = 0; i < m; i++) {
pref[i].second = suf[i].second = i;
cin >> pref[i].first >> suf[i].first;
reverse(suf[i].first.begin(), suf[i].first.end());
}
solvePrefix();
solveSuffix();
for (int i = 0; i < m; i++) {
int cnt = 0;
for (int j = 0; j < n; j++) {
if (ans[i][j] == 2) cnt++;
}
cout << cnt << '\n';
}
return 0;
}
