#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 5, maxC = 2e6 + 5;
int convert[26], ans[maxN]; string S[maxN];
namespace pref {
int to[maxC][4], mn[maxC], mx[maxC], currNode = 0;
void add_string(string s, int id) {
int u = 0;
for (auto ch: s) {
int x = ch - 'A'; x = convert[x];
if (!to[u][x]) to[u][x] = ++currNode;
u = to[u][x];
mx[u] = id; if (!mn[u]) mn[u] = id;
}
}
pair <int, int> get(string s) {
int u = 0;
for (auto ch: s) {
int x = ch - 'A'; x = convert[x];
if (!to[u][x]) return {-1, -1};
u = to[u][x];
}
return {mn[u], mx[u]};
}
}
namespace suff {
int to[maxC][4], cnt[maxC], currNode = 0;
void add_string(string S) {
int u = 0;
for (int i = S.size() - 1; i >= 0; i--) {
int x = S[i] - 'A'; x = convert[x];
if (!to[u][x]) to[u][x] = ++currNode;
u = to[u][x]; cnt[u]++;
}
}
void delete_string(string S) {
int u = 0;
for (int i = S.size() - 1; i >= 0; i--) {
int x = S[i] - 'A'; x = convert[x];
u = to[u][x]; cnt[u]--;
}
}
int get(string S) {
int u = 0;
for (int i = S.size() - 1; i >= 0; i--) {
int x = S[i] - 'A'; x = convert[x];
if (!to[u][x]) return 0;
u = to[u][x];
}
return cnt[u];
}
}
struct event {
string P, Q;
int id;
bool operator < (const event& rhs) const {
return P < rhs.P;
}
} query[maxN];
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
convert[0] = 0; convert[2] = 1; convert[6] = 2; convert[20] = 3;
int n, TiaChem;
cin >> n >> TiaChem;
for (int i = 1; i <= n; i++)
cin >> S[i];
sort(S + 1, S + n + 1);
for (int i = 1; i <= n; i++) {
pref::add_string(S[i], i);
//cout << i << ' ' << S[i] << '\n';
}
for (int i = 1; i <= TiaChem; i++) {
cin >> query[i].P >> query[i].Q;
query[i].id = i;
}
sort(query + 1, query + TiaChem + 1);
//cout << '\n';
int L = 1, R = 0;
for (int i = 1; i <= TiaChem; i++) {
pair<int, int> range = pref::get(query[i].P);
//cout << query[i].P << ' ' << query[i].Q << ' ' << range.first << ' ' << range.second << '\n';
if (range.first == -1) {
ans[query[i].id] = 0;
continue;
}
while (R < range.second) suff::add_string(S[++R]);
while (R > range.second) suff::delete_string(S[R--]);
while (L < range.first) suff::delete_string(S[L++]);
//cout << L << ' ' << R << '\n';
ans[query[i].id] = suff::get(query[i].Q);
}
for (int i = 1; i <= TiaChem; i++)
cout << ans[i] << '\n';
return 0;
}
