#include <bits/stdc++.h>
using namespace std;
int toInt(char c) {
static const char alpha[] = "AGCU";
int res = 0;
for (; alpha[res] != c; res++);
return res;
}
const int MAXN = 1.1e5;
const int MAXQ = 1.1e5;
int N, Q;
const int MAXL = 1.1e5;
char S[MAXL];
struct trie {
trie* ch[4];
int st, en;
};
trie* ROOTS[2];
trie* tnull;
void initTrie() {
for (int flip = 0; flip < 2; flip++) {
ROOTS[flip] = new trie();
}
tnull = new trie();
}
trie* insert(int len, trie* r) {
for (int i = 0; i < len; i++) {
int c = S[i];
if (r->ch[c] == NULL) {
r->ch[c] = new trie();
}
r = r->ch[c];
}
return r;
}
trie* query(int len, trie* r) {
for (int i = 0; i < len; i++) {
int c = S[i];
if (r->ch[c] == NULL) {
return tnull;
}
r = r->ch[c];
}
return r;
}
trie* locs[MAXN][2];
void dfs(trie* r, int& ind) {
if (r == NULL) return;
r->st = ind++;
for (int c = 0; c < 4; c++) {
dfs(r->ch[c], ind);
}
r->en = ind;
}
const int MAXV = 2.1e6;
int coords[MAXN][2];
int V[2] = {0, 0};
vector<int> pts[MAXV];
struct seg {
seg* ch[2];
int val;
};
seg* null;
void initSeg() {
null = new seg();
null->ch[0] = null->ch[1] = null;
null->val = 0;
}
seg* segs[MAXV];
seg* update(int p, seg* r, int x = 0, int y = V[1]) {
seg* n = new seg(*r);
n->val++;
if (y - x > 1) {
int z = (x + y) / 2;
if (p < z) {
n->ch[0] = update(p, r->ch[0], x, z);
} else {
n->ch[1] = update(p, r->ch[1], z, y);
}
}
return n;
}
int query(int l, int r, seg* n, int x = 0, int y = V[1]) {
int res = 0;
if (n != null) {
if (l <= x && y <= r) {
res = n->val;
} else {
int z = (x + y) / 2;
if (l < z) {
res += query(l, r, n->ch[0], x, z);
}
if (z < r) {
res += query(l, r, n->ch[1], z, y);
}
}
}
return res;
}
bool inRange(int a, int mi, int ma) {
return mi <= a && a < ma;
}
int querySlow(int xlo, int xhi, int ylo, int yhi) {
int res = 0;
for (int i = 0; i < N; i++) {
res += inRange(coords[i][0], xlo, xhi) && inRange(coords[i][1], ylo, yhi);
}
return res;
}
int query(int xlo, int xhi, int ylo, int yhi) {
assert(xlo <= xhi && ylo <= yhi);
// return querySlow(xlo, xhi, ylo, yhi);
return query(ylo, yhi, segs[xhi]) - query(ylo, yhi, segs[xlo]);
}
int main() {
scanf("%d %d", &N, &Q);
initTrie();
for (int i = 0; i < N; i++) {
scanf("%s", S);
int len = int(strlen(S));
for (int j = 0; j < len; j++) {
S[j] = toInt(S[j]);
}
for (int flip = 0; flip < 2; flip++) {
locs[i][flip] = insert(len, ROOTS[flip]);
reverse(S, S + len);
}
}
for (int flip = 0; flip < 2; flip++) {
int ind = 0;
dfs(ROOTS[flip], ind);
}
for (int i = 0; i < N; i++) {
for (int flip = 0; flip < 2; flip++) {
coords[i][flip] = locs[i][flip]->st;
V[flip] = max(V[flip], coords[i][flip] + 1);
}
pts[coords[i][0]].push_back(coords[i][1]);
}
initSeg();
segs[0] = null;
for (int x = 0; x < V[0]; x++) {
segs[x+1] = segs[x];
for (size_t i = 0; i < pts[x].size(); i++) {
int y = pts[x][i];
assert(y < V[1]);
segs[x+1] = update(y, segs[x+1]);
}
}
for (int q = 0; q < Q; q++) {
trie* Slocs[2];
for (int flip = 0; flip < 2; flip++) {
scanf("%s", S);
int len = int(strlen(S));
for (int j = 0; j < len; j++) {
S[j] = toInt(S[j]);
}
if (flip) {
reverse(S, S + len);
}
Slocs[flip] = query(len, ROOTS[flip]);
}
int ans = query(Slocs[0]->st, Slocs[0]->en, Slocs[1]->st, Slocs[1]->en);
printf("%d\n", ans);
}
return 0;
}
