#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
int trie[N][26];
int trier[N][26];
pair<int, int> d[N];
vector<int> dr[N];
string a[N];
int cnt = 0;
void add(string& s, int j) {
int curr = 0;
for (int i = 0; i < s.length(); i++) {
if (!trie[curr][s[i]-'A']) {
trie[curr][s[i]-'A'] = ++cnt;
}
curr = trie[curr][s[i]-'A'];
d[curr].first = min(d[curr].first, j);
d[curr].second = max(d[curr].second, j);
}
}
pair<int, int> get(string& s) {
int curr = 0;
for (int i = 0; i < s.length(); i++) {
if (!trie[curr][s[i] - 'A']) return {-1, -1};
curr = trie[curr][s[i] - 'A'];
}
return d[curr];
}
int cntr = 0;
void addr(string& s, int j) {
int curr = 0;
for (int i = s.length()-1; i >= 0; i--) {
if (!trier[curr][s[i]-'A']) {
trier[curr][s[i]-'A'] = ++cntr;
}
curr = trier[curr][s[i]-'A'];
dr[curr].push_back(j);
}
}
int getr(string& s, pair<int, int> range) {
int curr = 0;
for (int i = s.length()-1; i >= 0; i--) {
if (!trier[curr][s[i]-'A']) return 0;
curr = trier[curr][s[i]-'A'];
}
return upper_bound(dr[curr].begin(), dr[curr].end(), range.second) - lower_bound(dr[curr].begin(), dr[curr].end(), range.first);
}
signed main() {
cin.tie(0)->sync_with_stdio(false);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a+1, a+n+1);
fill(d, d+N, make_pair(n+1, 0));
for (int i = 1; i <= n; i++) {
add(a[i], i);
addr(a[i], i);
}
for (int i = 0; i < N; i++) {
sort(dr[i].begin(), dr[i].end());
}
string p, q;
while (m--) {
cin >> p >> q;
auto range = get(p);
cout << getr(q, range) << '\n';
}
return 0;
}
