#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
const int maxn = 1e5 + 5;
const int N = 2e6 + 6;
int n;
string s[maxn];
int q;
int ids[maxn];
vector<int> mrtee[N];
int tin[N], tout[N];
int timer;
struct node {
int child[4];
int exist;
node() {
memset(child, -1, sizeof(child));
exist = 0;
}
} root[N], root_suffix[N];
int num_nodes;
int add_prefix(string &s) {
int p = 0;
for(int i = 0; i < (int)s.size(); ++i) {
int c = s[i] - 'a';
if(root[p].child[c] == -1) {
root[p].child[c] = ++num_nodes;
}
p = root[p].child[c];
}
++root[p].exist;
return p;
}
int suffix_nodes;
void add_suffix(string &s, int id) {
int p = 0;
for(int i = (int)s.size() - 1; i >= 0; --i) {
int c = s[i] - 'a';
if(root_suffix[p].child[c] == -1) {
root_suffix[p].child[c] = ++suffix_nodes;
}
p = root_suffix[p].child[c];
mrtee[p].push_back(tin[id]);
}
}
int find_prefix(string &s) {
int p = 0;
for(int i = 0; i < (int)s.size(); ++i) {
int c = s[i] - 'a';
if(root[p].child[c] == -1) {
return -1;
}
p = root[p].child[c];
}
return p;
}
void build() {
for(int i = 1; i <= suffix_nodes; ++i) {
if((int)mrtee[i].size() < 2) continue;
sort(mrtee[i].begin(), mrtee[i].end());
}
}
int get_suffix(string &s, int l, int r) {
int p = 0;
for(int i = (int)s.size() - 1; i >= 0; --i) {
int c = s[i] - 'a';
if(root_suffix[p].child[c] == -1) {
return 0;
}
p = root_suffix[p].child[c];
}
return upper_bound(mrtee[p].begin(), mrtee[p].end(), r) -
lower_bound(mrtee[p].begin(), mrtee[p].end(), l);
}
void dfs(int u) {
tin[u] = ++timer;
for(int c = 0; c < 4; ++c) {
if(root[u].child[c] != -1) {
dfs(root[u].child[c]);
}
}
tout[u] = timer;
}
void convert(string &s) {
for(auto &c:s) {
if(c == 'A') c = 'a';
else if(c == 'U') c = 'b';
else if(c == 'G') c = 'c';
else c = 'd';
}
}
void solve() {
cin >> n >> q;
for(int i = 1; i <= n; ++i) {
cin >> s[i];
convert(s[i]);
ids[i] = add_prefix(s[i]);
}
dfs(0);
for(int i = 1; i <= n; ++i) {
add_suffix(s[i], ids[i]);
}
build();
debug(num_nodes, suffix_nodes);
string qp, qq;
for(int i = 1; i <= q; ++i) {
cin >> qp >> qq;
convert(qp), convert(qq);
int cur = find_prefix(qp);
if(cur == -1) {
cout << 0 << '\n';
continue;
}
cout << get_suffix(qq, tin[cur], tout[cur]) << '\n';
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
