#include <bits/stdc++.h>
using namespace std;
int n, q;
const int MXN = 100005;
string arr[MXN];
vector<pair<string, int>> proc;
string pre, suf;
bool usep;
bool after(int x) {
if (usep) {
for (int i=0; i<min(pre.size(), arr[x].size()); i++) {
if (pre[i] < arr[x][i]) return true;
if (pre[i] > arr[x][i]) return false;
}
return arr[x].size() >= pre.size();
}
else {
for (int i=0; i<min(suf.size(), proc[x].first.size()); i++) {
if (suf[i] < proc[x].first[i]) return true;
if (suf[i] > proc[x].first[i]) return false;
}
return proc[x].first.size() >= suf.size();
}
}
int first() {
if (!after(n)) return n + 1;
int low = 1;
int high = n;
while (low < high) {
int mid = (low + high) / 2;
if (after(mid)) {
high = mid;
}
else {
low = mid + 1;
}
}
return low;
}
vector<int> vec[MXN*4];
void build(int ind, int l, int r) {
for (int x=l; x<=r; x++) {
vec[ind].push_back(proc[x].second);
}
sort(vec[ind].begin(), vec[ind].end());
if (l == r) {
return;
}
int m = (l + r) / 2;
build(ind*2, l, m);
build(ind*2+1, m+1, r);
}
int LB, RB;
int query(int ind, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
return upper_bound(vec[ind].begin(), vec[ind].end(), RB) - lower_bound(vec[ind].begin(), vec[ind].end(), LB);
}
if (ql > r || qr < l) return 0;
int m = (l + r) / 2;
return query(ind*2, l, m, ql, qr) + query(ind * 2 + 1, m+1, r, ql, qr);
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> q;
for (int i=1; i<=n; i++) {
cin >> arr[i];
}
sort(arr+1, arr+n+1);
for (int i=1; i<=n; i++) {
string s = arr[i];
reverse(s.begin(), s.end());
proc.push_back({s, i});
}
proc.push_back({"", -1});
sort(proc.begin(), proc.end());
build(1, 1, n);
while (q--) {
cin >> pre >> suf;
reverse(suf.begin(), suf.end());
usep = true;
int pre_a = first();
pre += 'a';
int pre_b = first() - 1;
usep = false;
int suf_a = first();
suf += 'a';
int suf_b = first() - 1;
LB = pre_a;
RB = pre_b;
if (LB > RB) {
cout << 0 << endl;
continue;
}
cout << query(1, 1, n, suf_a, suf_b) << endl;
}
}
