#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()
template<class S, class T>
bool chmin(S &a, const T &b) {
return a > b && (a = b) == b;
}
template<class S, class T>
bool chmax(S &a, const T &b) {
return a < b && (a = b) == b;
}
const int inf = 1e9 + 7;
const int INF = 1e18 + 7;
const int mod = 998244353;
struct Trie {
map<char, Trie*> children;
vector<int> v;
int pref;
bool end;
Trie() {
pref = 0;
end = false;
}
};
void insert(Trie *root, string rna, int ind) {
Trie *cur = root;
for (int i = 0; i < size(rna); i++) {
Trie *node = cur->children[rna[i]];
if (!node) {
node = new Trie();
cur->children[rna[i]] = node;
}
cur = node;
cur->pref++;
cur->v.push_back(ind);
}
cur->end = true;
}
int get(Trie *root, string rna, int l, int r) {
Trie *cur = root;
for (int i = 0; i < size(rna); i++) {
Trie *node = cur->children[rna[i]];
if (!node) {
return 0;
}
cur = node;
}
return (upper_bound(all(cur->v), r) - cur->v.begin()) - (lower_bound(all(cur->v), l) - cur->v.begin());
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
Trie *root = new Trie();
int n, m;
cin >> n >> m;
string s[n];
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
sort(s, s + n);
for (int i = 0; i < n; ++i) {
reverse(all(s[i]));
insert(root, s[i], i);
reverse(all(s[i]));
}
while (m--) {
string p, q;
cin >> p >> q;
reverse(all(q));
int l = 0, r = n - 1;
for (int i = 0; i < size(p); ++i) {
int lo = l - 1, hi = r + 1;
while (lo + 1 < hi) {
int mid = (lo + hi) >> 1;
if (size(s[mid]) < i + 1) {
lo = mid;
} else {
if (s[mid][i] < p[i]) {
lo = mid;
} else {
hi = mid;
}
}
}
int low = lo + 1;
lo = l - 1, hi = r + 1;
while (lo + 1 < hi) {
int mid = (lo + hi) >> 1;
if (size(s[mid]) < i + 1) {
lo = mid;
} else {
if (s[mid][i] <= p[i]) {
lo = mid;
} else {
hi = mid;
}
}
}
int high = hi - 1;
l = low, r = high;
if (l > r) {
break;
}
}
if (l > r) {
cout << 0 << '\n';
continue;
}
cout << get(root, q, l, r) << '\n';
}
}
