#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9;
void transform(string &str) {
for (char &c: str) {
if (c == 'A') c = 'a';
else if (c == 'G') c = 'b';
else if (c == 'C') c = 'c';
else c = 'd';
}
}
struct node {
int sz = 0, mn = inf, mx = -inf, go[4] = {-1, -1, -1, -1};
node() = default;
};
vector<node> t = {{}};
void add(string &str, int key) {
int v = 0;
for (int i = 0; i < (int) str.size(); ++i) {
int c = str[i] - 'a';
if (t[v].go[c] == -1) {
t.emplace_back();
t[v].go[c] = (int) t.size() - 1;
}
t[v].sz += 1;
t[v].mn = min(t[v].mn, key);
t[v].mx = max(t[v].mx, key);
v = t[v].go[c];
}
t[v].sz += 1;
t[v].mn = min(t[v].mn, key);
t[v].mx = max(t[v].mx, key);
}
int find(string &str) {
int v = 0;
for (int i = 0; i < (int) str.size() && v != -1; ++i) {
v = t[v].go[str[i] - 'a'];
}
return v;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<string> s(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
transform(s[i]);
}
sort(s.begin(), s.end());
vector<string> a(m), b(m);
vector<int> ans(m);
vector<vector<pair<int, int>>> qu(n);
for (int i = 0; i < m; ++i) {
cin >> a[i] >> b[i];
transform(a[i]), transform(b[i]);
reverse(b[i].begin(), b[i].end());
}
for (int i = 0; i < n; ++i) {
add(s[i], i);
}
for (int i = 0; i < m; ++i) {
int v = find(a[i]);
if (v == -1) {
continue;
}
assert(t[v].sz == t[v].mx - t[v].mn + 1);
if (t[v].mn > 0) {
qu[t[v].mn - 1].emplace_back(i, -1);
}
qu[t[v].mx].emplace_back(i, 1);
}
t = {{}};
for (int i = 0; i < n; ++i) {
reverse(s[i].begin(), s[i].end());
add(s[i], i);
for (auto [j, k] : qu[i]) {
int v = find(b[j]);
if (v != -1) {
ans[j] += k * t[v].sz;
}
}
}
for (int i = 0; i < m; ++i) {
cout << ans[i] << '\n';
}
return 0;
}
