#include <bits/stdc++.h>
using namespace std;
const int N = 5'000 + 10,
base = 19937;
int n, m;
using ull = unsigned long long;
ull pw[N];
struct Hash {
int n;
vector<ull> h;
Hash() {}
Hash(string s) : n(s.size()), h(s.size() + 1) {
pw[0] = 1;
for (int i = 1; i <= n; ++i) {
h[i] = h[i - 1] * base + s[i - 1];
pw[i] = pw[i - 1] * base;
}
}
ull get(int l, int r) { return h[r] - h[l - 1] * pw[r - l + 1]; }
} h[N];
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
string s; cin >> s;
h[i] = Hash(s);
}
while (m--) {
string st, ed; cin >> st >> ed;
Hash s(st), e(ed);
int answer = 0;
for (int i = 1; i <= n; ++i) {
if (h[i].n < s.n || h[i].n < e.n) continue;
answer += (h[i].get(1, s.n) == s.get(1, s.n)
&& h[i].get(h[i].n - e.n + 1, h[i].n) == e.get(1, e.n));
}
cout << answer << "\n";
}
}
