#include <bits/stdc++.h>
using namespace std;
const int N = 2000001, A = 4;
const string R = "AGCU";
int suffix[N][A], prefix[N][A], root[N], sub[N], ans[N];
vector<pair<int, vector<int>>> queries[N];
vector<int> read() {
string s;
cin >> s;
vector<int> ans;
for (auto c : s) {
ans.push_back(find(R.begin(), R.end(), c) - R.begin());
}
return ans;
}
int merge(int u, int v) {
if (u == 0 || v == 0) {
return u > 0 ? u : v;
} else {
sub[u] += sub[v];
for (int i = 0; i < A; ++i) {
suffix[u][i] = merge(suffix[u][i], suffix[v][i]);
}
return u;
}
}
void dfs(int u) {
for (auto c : prefix[u]) {
if (c > 0) {
dfs(c);
root[u] = merge(root[u], root[c]);
}
}
for (auto &[i, q] : queries[u]) {
int v = root[u];
for (auto c : q) {
v = suffix[v][c];
}
ans[i] = sub[v];
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
int x = 1, y = 1;
for (int i = 0; i < n; ++i) {
vector<int> s = read();
int u = 0;
for (auto c : s) {
if (prefix[u][c] == 0) {
prefix[u][c] = x++;
}
u = prefix[u][c];
}
if (root[u] == 0) {
root[u] = y++;
}
reverse(s.begin(), s.end());
u = root[u];
++sub[u];
for (auto c : s) {
if (suffix[u][c] == 0) {
suffix[u][c] = y++;
}
u = suffix[u][c];
++sub[u];
}
}
for (int i = 0; i < m; ++i) {
vector<int> p = read(), q = read();
int u = 0;
for (auto c : p) {
u = prefix[u][c];
}
if (u > 0) {
reverse(q.begin(), q.end());
queries[u].push_back({i, q});
}
}
dfs(0);
for (int i = 0; i < m; ++i) {
cout << ans[i] << "\n";
}
}
