#include <bits/stdc++.h>
using namespace std;
const int N = (int)1e5 + 7;
int n, m;
string s[N], t[N];
int toint[200];
struct node {
int to[4];
int ind, l, r, pr;
node() {
l = N;
r = 0;
memset(to, -1, sizeof to);
}
};
node st[(int)2e6 + 7];
int ar[N];
int sz;
int add(string &t, int j) {
int cur = 0;
for (int i = 0; i < t.size(); i++) {
if (st[cur].to[toint[t[i]]] == -1) {
st[cur].to[toint[t[i]]] = ++sz;
st[sz].pr = cur;
}
cur = st[cur].to[toint[t[i]]];
}
reverse(t.begin(), t.end());
st[cur].ind = lower_bound(s + 1, s + n + 1, t) - s;
reverse(t.begin(), t.end());
int temp = cur;
while (cur) {
st[cur].r = max(st[cur].r, j);
st[cur].l = min(st[cur].l, j);
cur = st[cur].pr;
}
return st[temp].ind;
}
int root[N];
struct seg {
int l, r, val;
seg() {
l = r = val = 0;
}
};
seg tree[N * 30];
void build(int v = 1, int l = 1, int r = n) {
tree[v].val = 0;
if (l == r) {
return ;
}
int mid = (l + r) >> 1;
tree[v].l = ++sz;
tree[v].r = ++sz;
build(tree[v].l, l, mid);
build(tree[v].r, mid + 1, r);
}
void upd(int nv, int ov, int pos, int l = 1, int r = n) {
tree[nv].val = tree[ov].val;
if (l == r) {
tree[nv].val++;
return ;
}
int mid = (l + r) >> 1;
if (pos <= mid) {
tree[nv].l = ++sz;
tree[nv].r = tree[ov].r;
upd(tree[nv].l, tree[ov].l, pos, l, mid);
} else {
tree[nv].l = tree[ov].l;
tree[nv].r = ++sz;
upd(tree[nv].r, tree[ov].r, pos, mid + 1, r);
}
tree[nv].val = tree[tree[nv].l].val + tree[tree[nv].r].val;
}
int get(int nv, int ov, int l, int r, int tl = 1, int tr = n) {
if (tl > r || tr < l) return 0;
if (l <= tl && tr <= r) return tree[nv].val - tree[ov].val;
int mid = (tl + tr) >> 1;
return get(tree[nv].l, tree[ov].l, l, r, tl, mid) + get(tree[nv].r, tree[ov].r, l, r, mid + 1, tr);
}
main() {
toint['A'] = 0;
toint['G'] = 1;
toint['C'] = 2;
toint['U'] = 3;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
cin >> s[i];
t[i] = s[i];
reverse(t[i].begin(), t[i].end());
}
sort(s + 1, s + n + 1);
sort(t + 1, t + n + 1);
for (int i = 1; i <= n; i++) {
ar[i] = add(t[i], i);
}
root[0] = 1;
sz = 0;
build();
for (int i = 1; i <= n; i++) {
root[i] = ++sz;
upd(root[i], root[i - 1], ar[i]);
}
while (m--) {
string S, T;
cin >> S >> T;
int l = lower_bound(s + 1, s + n + 1, S) - s;
S += '[';
int r = upper_bound(s + 1, s + n + 1, S) - s - 1;
if (l > r) {
puts("0");
continue;
}
reverse(T.begin(), T.end());
int L, R;
L = lower_bound(t + 1, t + n + 1, T) - t;
T += '[';
R = upper_bound(t + 1, t + n + 1, T) - t - 1;
if (L > R) {
puts("0");
continue;
}
//cout << l << ' ' << r << ' ' << L << ' ' << R << endl;
printf("%d\n", get(root[R], root[L - 1], l, r));
}
}
