#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"; } }