#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
const int K = 4;
const int MX = 2e6 + 10;
struct node {
vector<int> nxt, who;
int sz;
node() { nxt = vector<int>(K, -1); who = {}; sz = 0; }
};
template<int MX> struct Trie {
int cur = 1;
node T[MX];
void add(const string &S, int IDX) {
int v = 0;
for(auto c : S) {
if (T[v].nxt[c-'A'] == -1) {
T[v].nxt[c-'A'] = cur++;
}
T[v].sz++;
T[v].who.push_back(IDX);
v = T[v].nxt[c-'A'];
}
T[v].sz++;
T[v].who.push_back(IDX);
}
array<int, 2> query(const string &S) {
int v = 0;
for(auto c : S) {
if (T[v].nxt[c-'A'] == -1) return {-1, -1};
v = T[v].nxt[c-'A'];
}
return {T[v].who.front(), T[v].who.back()};
}
int query(const string &S, int L, int R) {
int v = 0;
for(auto c : S) {
if (T[v].nxt[c-'A'] == -1) return 0;
v = T[v].nxt[c-'A'];
}
return int(upper_bound(begin(T[v].who), end(T[v].who), R) - lower_bound(begin(T[v].who), end(T[v].who), L));
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
Trie<MX> pfx, sfx;
auto alter = [&](string &S) {
for(auto &c : S) {
if (c == 'U') c = 'D';
if (c == 'G') c = 'B';
}
};
int N, Q; cin >> N >> Q;
vector<string> A;
for(int i = 0; i < N; i++) {
string s; cin >> s; alter(s);
A.push_back(s);
}
sort(begin(A), end(A));
for(int i = 0; i < N; i++) {
pfx.add(A[i], i);
reverse(begin(A[i]), end(A[i]));
sfx.add(A[i], i);
}
while(Q--) {
string p, s; cin >> p >> s; alter(p); alter(s);
reverse(begin(s), end(s));
auto [L, R] = pfx.query(p);
cout << sfx.query(s, L, R) << nl;
}
return 0;
}
