#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
int idx;
vector<pair<int, int>> a;
vector<int> nxt;
node(int i) { idx = i, nxt.resize(26, -1); }
};
string strip(string& s, int k) { string t; for (int i = 0; i < min((int)s.length(), k); ++i) t += s[i]; return t; }
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n, q, m = 1; cin >> n >> q;
vector<string> a(n);
for (auto &x : a) cin >> x;
sort(a.begin(), a.end());
vector<node> arr;
arr.push_back((0));
for (int i = 0; i < n; ++i) {
int cur = 0, mi = a[i].length();
arr[cur].a.push_back({ i, arr[cur].a.size() });
for (int k = 0; k < mi; ++k) {
int j = (mi - k - 1);
if (arr[cur].nxt[(a[i][j] - 'A')] == -1)
arr[cur].nxt[(a[i][j] - 'A')] = m, arr.push_back((m)), cur = m, m++;
else cur = arr[cur].nxt[(a[i][j] - 'A')];
arr[cur].a.push_back({ i, arr[cur].a.size() });
}
}
while (q--) {
string s, t; cin >> s >> t;
reverse(t.begin(), t.end());
int l = 0, r = n - 1, si = n, ei = 0;
while (l <= r) {
int m = (l + r) / 2;
if (strip(a[m], s.length()) < s) l = m + 1;
else si = m, r = m - 1;
}
l = 0, r = n - 1;
while (l <= r) {
int m = (l + r) / 2;
if (strip(a[m], s.length()) > s) r = m - 1;
else ei = m, l = m + 1;
}
int idx = 0;
for (int i = 0; i < t.length(); ++i) {
if (idx == -1) break;
idx = arr[idx].nxt[t[i] - 'A'];
}
if ((idx == -1) || (si > ei)) { cout << 0 << endl; continue; }
auto f = lower_bound(arr[idx].a.begin(), arr[idx].a.end(), make_pair(si, -1));
auto e = lower_bound(arr[idx].a.begin(), arr[idx].a.end(), make_pair(ei, n + n));
if ((f == arr[idx].a.end()) || (e == arr[idx].a.begin())) { cout << 0 << endl; continue; }
cout << ((*prev(e)).second - (*f).second + 1) << endl;
}
}
