#include <bits/stdc++.h>
#define long long long
using namespace std;
const int N = (int) 1E5;
const int K = (int) 2E6;
int index(char c) {
if (c == 'A') {
return 0;
}
if (c == 'G') {
return 1;
}
if (c == 'C') {
return 2;
}
if (c == 'U') {
return 3;
}
return -1;
}
int x[2];
int e[2][K + 1][4];
int l[K + 1], r[K + 1];
vector<int> a[K + 1];
void insert(string s, int p, int t) {
int u = 0;
for (int i = 0; i < (int) s.size(); i++) {
if (t == 0) {
l[u] = l[u] >= 0 ? l[u] : p;
r[u] = max(r[u], p);
} else {
a[u].push_back(p);
}
int &v = e[t][u][index(s[i])];
if (v == 0) {
v = ++x[t];
}
u = v;
}
if (t == 0) {
l[u] = l[u] >= 0 ? l[u] : p;
r[u] = max(r[u], p);
} else {
a[u].push_back(p);
}
}
int find(string s, int t) {
int u = 0;
for (int i = 0; i < (int) s.size(); i++) {
int v = e[t][u][index(s[i])];
if (v == 0) {
return -1;
}
u = v;
}
return u;
}
int n, k;
string s[N];
int main() {
#ifdef LOCAL
freopen("A.in", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> s[i];
}
sort(s, s + n);
memset(l, -1, sizeof(l));
for (int i = 0; i < n; i++) {
insert(s[i], i, 0);
reverse(s[i].begin(), s[i].end());
insert(s[i], i, 1);
}
for (int i = 0; i < k; i++) {
string t0, t1;
cin >> t0 >> t1;
reverse(t1.begin(), t1.end());
int p0 = find(t0, 0), p1 = find(t1, 1);
if (p0 < 0 || p1 < 0) {
cout << 0 << "\n";
} else {
auto i0 = upper_bound(a[p1].begin(), a[p1].end(), r[p0]);
auto i1 = lower_bound(a[p1].begin(), a[p1].end(), l[p0]);
cout << (int) (i0 - i1) << "\n";
}
}
return 0;
}
