#include <iostream>
#include <string>
using namespace std;
const int M = 2e6 + 10;
const int C = 16;
int n, m, x, y;
string s, pre, suf;
struct Trie {
struct node {
int child[C], cnt;
node () {
fill_n(child, C, -1);
}
} nd[M];
int root, cnt;
Trie () {
root = cnt = 0;
}
void NewNode(int u, int c) {
nd[u].child[c] = ++cnt;
}
void add() {
int cur = root, kk = s.size();
for (int i = 0; i < kk; ++i) {
int c = (s[i] - 'A') << 2 | (s[kk - i - 1] - 'A');
if (nd[cur].child[c] == -1) NewNode(cur, c);
cur = nd[cur].child[c];
++nd[cur].cnt;
}
}
void calc(int i, int cur, int &ans) {
if (cur == -1) return;
if (i == max(x, y)) {
ans += nd[cur].cnt;
return;
}
if (i < min(x, y)) {
int c = (pre[i] - 'A') << 2 | (suf[y - i - 1] - 'A');
calc(i + 1, nd[cur].child[c], ans);
} else {
if (i < x) {
int Fix = (pre[i] - 'A') << 2;
for (int j = 0; j < 4; ++j) {
calc(i + 1, nd[cur].child[Fix + j], ans);
}
} else {
int Fix = suf[y - i - 1] - 'A';
for (int j = 0; j <= 12; j += 4) {
calc(i + 1, nd[cur].child[j + Fix], ans);
}
}
}
}
} T;
void change(string &kk) {
for (int i = 0; i < kk.size(); ++i) {
if (kk[i] == 'U') kk[i] = 'B';
else if (kk[i] == 'G') kk[i] = 'D';
}
}
int main() {
//freopen("input.txt", "r", stdin);
cin.tie(0); cout.tie(0);
ios_base::sync_with_stdio(false);
cin >> n >> m;
while (n--) {
cin >> s;
change(s);
T.add();
}
while (m--) {
cin >> pre >> suf;
x = pre.size(); y = suf.size();
change(pre); change(suf);
int ans = 0;
T.calc(0, 0, ans);
cout << ans << "\n";
}
return 0;
}
