#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define index_set tree<pair<string, int>, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>
#define mid (l + r) / 2
#define child v * 2
const int N = 1e5;
vector<string> t[N * 4];
string s[N];
bool compatible(const string &a, const string &b) {
return a.substr(0, b.length()) == b;
}
string reverse(string a) {
reverse(a.begin(), a.end());
return a;
}
void build(int v, int l, int r) {
if (l == r) {
t[v].push_back(reverse(s[l]));
return;
}
build(child, l, mid);
build(child + 1, mid + 1, r);
int lp = 0, rp = 0;
while (lp != t[child].size() && rp != t[child + 1].size()) {
if (t[child][lp] < t[child + 1][rp])
t[v].push_back(t[child][lp++]);
else
t[v].push_back(t[child + 1][rp++]);
}
while (lp != t[child].size())
t[v].push_back(t[child][lp++]);
while (rp != t[child + 1].size())
t[v].push_back(t[child + 1][rp++]);
}
int query(int v, int l, int r, int tl, int tr, pair<string, int> &up, pair<string, int> &down) {
if (tl > tr)
return 0;
else if (l == tl && r == tr)
return (lower_bound(t[v].begin(), t[v].end(), up.first) - t[v].begin()) - (lower_bound(t[v].begin(), t[v].end(), down.first) - t[v].begin());
return query(child, l, mid, tl, min(mid, tr), up, down) + query(child + 1, mid + 1, r, max(mid + 1, tl), tr, up, down);
}
void solveTestCase() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> s[i];
sort(s, s + n);
build(1, 0, n - 1);
/*for (int i = 0; i < n; i++)
cout << s[i] << " ";
cout << endl;*/
for (int i = 0; i < m; i++) {
string p, q;
cin >> p >> q;
string temp = p;
temp[p.length() - 1]++;
int tl = lower_bound(s, s + n, p) - s, tr = lower_bound(s, s + n, temp) - s - 1;
temp = reverse(q);
temp[q.length() - 1]++;
pair<string, int> up = {temp, -1}, down = {reverse(q), -1};
cout << query(1, 0, n - 1, tl, tr, up, down) << "\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int test = 1;
// cin >> test;
while (test--)
solveTestCase();
}
