//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <stack>
#define ll long long
#define ff first
#define ss second
#define maxn 100005
#define mod 1000000007
#define zckorz ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
int n, m;
int cor[maxn], arr[maxn], ans[maxn];
struct node {
char c;
int cnt = 0, l, r;
node * chi[4];
vector<int> v;
node(char ch) {
c = ch, cnt = 0, l = 0, r = 0;
for (int i = 0;i < 4;i++) chi[i] = NULL;
}
node() {
c = ' ', cnt = 0, l = 0, r = 0;
for (int i = 0;i < 4;i++) chi[i] = NULL;
}
};
void add(node * cur, string &s, int ind, int x) {
//cout << cur->c;
if (ind == s.size() - 1) {
cur->cnt++;
cur->v.push_back(x);
return;
}
//cout << s << " " << ind << endl;
int nxt = s[ind + 1] - 'A';
if (cur->chi[nxt] == NULL) {
node * add = new node(s[ind + 1]);
cur->chi[nxt] = add;
}
add(cur->chi[nxt], s, ind + 1, x);
}
void print(node * cur, int dep) {
//cout << 7122 << endl;
for (int i = 0;i < dep;i++) cout << " ";
cout << cur->c << endl;
for (int i = 0;i < 4;i++) {
if (cur->chi[i] != NULL) {
//cout << 11 << endl;
print(cur->chi[i], dep + 1);
}
}
}
int ind = 0;
void dfs(node * cur) {
cur->l = ind;
for (int x:cur->v) {
cor[x] = ind++;
}
for (int i = 0;i < 4;i++) {
if (cur->chi[i] != NULL) {
dfs(cur->chi[i]);
}
}
cur->r = ind;
}
void dfs2(node * cur) {
cur->l = ind;
for (int x:cur->v) {
arr[ind++] = cor[x];
}
for (int i = 0;i < 4;i++) {
if (cur->chi[i] != NULL) {
dfs2(cur->chi[i]);
}
}
cur->r = ind;
}
pair<int, int> range(node * cur, string & s, int ind) {
if (ind == s.size() - 1) {
return make_pair(cur->l, cur->r);
}
int nxt = s[ind + 1] - 'A';
if (cur->chi[nxt] == NULL) {
return make_pair(-1, -1);
} else {
return range(cur->chi[nxt], s, ind + 1);
}
}
node * pref = new node(), * suf = new node();
struct ev{
int y, id;
bool pos;
ev(int b, int c, bool d) {
y = b, id = c, pos = d;
}
};
vector<ev> que[maxn];
int bit[maxn];
void modify(int ind, int val) {
ind++;
for (;ind < maxn;ind += ind & (-ind)) bit[ind] += val;
}
int query(int ind) {
ind++;
if (ind < 0) return 0;
int ret = 0;
for (;ind > 0;ind -= ind & (-ind)) ret += bit[ind];
return ret;
}
int main() {
zckorz
cin >> n >> m;
for (int i = 0;i < n;i++) {
string s;
cin >> s;
for (int j = 0;j < s.size();j++) s[j] = (s[j] == 'G' ? 'B' : (s[j] == 'U' ? 'D' : s[j]));
add(pref, s, -1, i);
//cout << endl;
reverse(s.begin(), s.end());
add(suf, s, -1, i);
//cout << endl;
}
dfs(pref);
ind = 0;
dfs2(suf);
//for (int i = 0;i < n;i++) cout << arr[i] << " ";
//cout << endl;
for (int i = 0;i < m;i++) {
string p, q;
cin >> p >> q;
for (int j = 0;j < p.size();j++) p[j] = (p[j] == 'G' ? 'B' : (p[j] == 'U' ? 'D' : p[j]));
for (int j = 0;j < q.size();j++) q[j] = (q[j] == 'G' ? 'B' : (q[j] == 'U' ? 'D' : q[j]));
reverse(q.begin(), q.end());
pair<int, int> r1 = range(pref, p, -1), r2 = range(suf, q, -1);
//cout << r2.ff << " " << r2.ss << " " << r1.ff << " " << r1.ss << endl;
if (r1.ff == -1 || r2.ff == -1) {
ans[i] = 0;
} else {
int l = r2.ff, r = r2.ss, x = r1.ff, y = r1.ss;
que[r - 1].push_back(ev(y - 1, i, true));
que[r - 1].push_back(ev(x - 1, i, false));
if (l) que[l - 1].push_back(ev(y - 1, i, false));
if (l) que[l - 1].push_back(ev(x - 1, i, true));
}
}
for (int i = 0;i < n;i++) {
modify(arr[i], 1);
for (auto j:que[i]) {
if (j.pos) {
ans[j.id] += query(j.y);
} else {
ans[j.id] -= query(j.y);
}
}
}
for (int i = 0;i < m;i++) cout << ans[i] << "\n";
//print(pref, 0);
}
