#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
const int N = 2e6 + 3;
int n, m;
string s, p, q;
vector<pair<string, int> > a, b;
int ans = 0;
//////////////////// Persistent IT
int nVer = 0;
struct Node {
int left, right; // ID of left child & right child
long long ln; // Max value of node
Node() {}
Node(long long ln, int left, int right) : ln(ln), left(left), right(right) {}
} it[1 << 21]; // Each node has a position in this array, called ID
int nNode;
const int MN = 1e5 + 3;
int ver[MN]; // ID of root in each version
// Update max value of a node
inline void refine(int cur) {
it[cur].ln = (it[it[cur].left].ln + it[it[cur].right].ln);
}
// Update a range, and return new ID of node
int update(int l, int r, int u, int x, int oldId) {
if (l == r) {
// cout << l << ' ' << x << ' ' << nNode + 1 << '\n';
++nNode;
it[nNode] = Node(x + it[nNode].ln, 0, 0);
return nNode;
}
int mid = (l + r) >> 1;
int cur = ++nNode;
if (u <= mid) {
it[cur].left = update(l, mid, u, x, it[oldId].left);
it[cur].right = it[oldId].right;
refine(cur);
}
else {
it[cur].left = it[oldId].left;
it[cur].right = update(mid+1, r, u, x, it[oldId].right);
refine(cur);
}
return cur;
}
// Get max of range. Same as usual IT
int get(int nodeId, int l, int r, int u, int v) {
if (v < l || r < u) return -1;
if (u <= l && r <= v) return it[nodeId].ln;
int mid = (l + r) >> 1;
return (get(it[nodeId].left, l, mid, u, v) + get(it[nodeId].right, mid+1, r, u, v));
}
//// When update:
// ++nVer;
// ver[nVer] = update(1, n, u, x, ver[nVer-1]);
//
//// When query:
// res = get(ver[t], 1, n, u, v);
int main () {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++ i) {
cin >> s;
a.push_back({s, i});
}
sort (a.begin(), a.end());
for (int i = 0; i < n; ++ i) {
s = a[i].fi;
reverse(s.begin(), s.end());
b.push_back({s, i});
}
sort (b.begin(), b.end());
for (auto [s, id] : b) {
++ nVer;
ver[nVer] = update(0, n - 1, id, 1, ver[nVer-1]);
}
// for (auto [s, id] : a) cout << s << '\n';
// for (auto [s, id] : b) cout << s << ' ' << id << '\n';
while (m --) {
cin >> p >> q;
reverse(q.begin(), q.end());
int l = lower_bound(a.begin(), a.end(), make_pair(p, -1)) - a.begin();
p.back() ++;
int r = lower_bound(a.begin(), a.end(), make_pair(p, -1)) - a.begin() - 1;
int tl = lower_bound(b.begin(), b.end(), make_pair(q, -1)) - b.begin();
q.back() ++;
int tr = lower_bound(b.begin(), b.end(), make_pair(q, -1)) - b.begin() - 1;
if (l >= a.size() || tl >= b.size()) {
cout << 0 << '\n';
continue;
}
// cout << l << ' ' << r << ' ' << tl << ' ' << tr + 1 << '\n';
cout << get(ver[tr + 1], 0, n-1, l, r) - get(ver[tl], 0, n-1, l, r) << '\n';
}
}
