#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 1e5;
vector <string> isi[MAXN+5];
string B[MAXN+5];
int ans[MAXN+5];
struct Trie {
int sum = 0;
int depth;
Trie *ch[4] = {NULL};
void add(string &s, int val) {
sum += val;
if (depth == s.size()-1) return;
if (ch[s[depth+1]-'A'] == NULL) {
ch[s[depth+1]-'A'] = new Trie();
ch[s[depth+1]-'A']->depth = depth+1;
}
ch[s[depth+1]-'A']->add(s, val);
}
int query(string &s) {
if (depth == s.size()-1) {
return sum;
}
if (ch[s[depth+1]-'A'] != NULL) {
return ch[s[depth+1]-'A']->query(s);
}
return 0;
}
void reset() {
for (int j = 0; j < 4; j++) ch[j] = NULL;
}
} tr;
struct Node {
Node *ch[4] = {NULL};
int depth, sz = 0, heavy = -1;
vector <string> isi;
vector <int> queries;
void add(string &s, string &b) {
if (depth == s.size()-1) {
isi.push_back(b);
return;
}
if (ch[s[depth+1]-'A'] == NULL) {
ch[s[depth+1]-'A'] = new Node();
ch[s[depth+1]-'A']->depth = depth+1;
}
ch[s[depth+1]-'A']->add(s, b);
}
void add_query(string &s, int idx) {
if (depth == s.size()-1) {
queries.push_back(idx);
return;
}
if (ch[s[depth+1]-'A'] != NULL) {
ch[s[depth+1]-'A']->add_query(s, idx);
}
}
void dfs() {
int MX = 0;
for (auto x : isi) sz += x.size();
for (int j = 0; j < 4; j++) {
if (ch[j] != NULL) {
ch[j]->dfs();
sz += ch[j]->sz;
if (ch[j]->sz > MX) {
MX = ch[j]->sz;
heavy = j;
}
}
}
}
void compute(bool solve, bool keep) {
if (solve) {
for (int j = 0; j < 4; j++) {
if (j != heavy && ch[j] != NULL) {
ch[j]->compute(1, 0);
}
}
}
if (heavy != -1) ch[heavy]->compute(solve, 1);
for (int j = 0; j < 4; j++) {
if (j != heavy && ch[j] != NULL) {
ch[j]->compute(0, 1);
}
}
for (auto x : isi) {
tr.add(x, 1);
}
if (solve) {
for (auto x : queries) {
ans[x] = tr.query(B[x]);
}
}
if (!keep) {
tr.reset();
}
}
};
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int N, M; cin >> N >> M;
Node tree;
tree.depth = -1;
for (int i = 1; i <= N; i++) {
string a; cin >> a;
for (auto &j : a) {
if (j == 'G') j = 'B';
if (j == 'U') j = 'D';
}
string b = a;
reverse(b.begin(), b.end());
tree.add(a, b);
}
tr.depth = -1;
for (int i = 1; i <= M; i++) {
string a, b; cin >> a >> b;
for (auto &j : a) {
if (j == 'G') j = 'B';
if (j == 'U') j = 'D';
}
for (auto &j : b) {
if (j == 'G') j = 'B';
if (j == 'U') j = 'D';
}
B[i] = b;
reverse(B[i].begin(), B[i].end());
tree.add_query(a, i);
}
tree.dfs();
tree.compute(1, 0);
for (int i = 1; i <= M; i++) cout << ans[i] << "\n";
}
/*
sack
*/
