#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <utility>
#define SZ (1<<21)
#define fi first
#define se second
using namespace std;
struct entry {
int i, l, r, f, a;
};
int N, M, ppos[100005], spos[100005], ans[100005];
string S[100005], P[100005], Q[100005];
vector<int> sw[2000005];
vector<entry> qu;
char bruh[] = { 'A', 'C', 'G', 'U' };
struct Trie {
int ch[2000005][4], cnt = 2, sz[2000005], ind[2000005], cnt2;
vector<int> occ[2000005];
void build(int s) {
int cur = 1;
for (char c : S[s]) {
for (int i = 0; i < 4; i++) {
if (c == bruh[i]) {
if (ch[cur][i] == 0) {
ch[cur][i] = cnt++;
}
cur = ch[cur][i];
}
}
}
occ[cur].push_back(s);
}
void dfs(int x, int *p) {
ind[x] = cnt2++;
sz[x] = 1;
for (int v : occ[x]) p[v] = ind[x];
for (int i = 0; i < 4; i++) {
if (ch[x][i]) {
dfs(ch[x][i], p);
sz[x] += sz[ch[x][i]];
}
}
}
int query(const string &s) {
int cur = 1;
for (char c : s) {
for (int i = 0; i < 4; i++) {
if (c == bruh[i]) {
if (ch[cur][i] == 0) {
return 0;
}
cur = ch[cur][i];
}
}
}
return cur;
}
} tp, ts;
struct Segtree {
int st[1<<22];
void seg_inc(int i) {
for (st[i += SZ] += 1; i > 1; i >>= 1) st[i>>1] = st[i] + st[i^1];
}
int seg_sum(int l, int r) {
int res = 0;
for (l += SZ, r += SZ; l < r; l >>= 1, r >>= 1) {
if (l&1) res += st[l++];
if (r&1) res += st[--r];
}
return res;
}
} st1;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
for (int i = 0; i < N; i++) {
cin >> S[i];
tp.build(i);
reverse(S[i].begin(), S[i].end());
ts.build(i);
}
tp.dfs(1, ppos);
ts.dfs(1, spos);
for (int i = 0; i < N; i++) {
//printf("Point at (%d, %d)\n", ppos[i], spos[i]);
sw[ppos[i]].push_back(spos[i]);
}
for (int i = 0; i < M; i++) {
cin >> P[i] >> Q[i];
reverse(Q[i].begin(), Q[i].end());
int pn = tp.query(P[i]);
int sn = ts.query(Q[i]);
int pl = tp.ind[pn];
int pr = tp.ind[pn] + tp.sz[pn];
int sl = ts.ind[sn];
int sr = ts.ind[sn] + ts.sz[sn];
//printf("Query %d: [%d, %d), [%d, %d)\n", i, pl, pr, sl, sr);
qu.push_back({ pl-1, sl, sr, -1, i });
qu.push_back({ pr-1, sl, sr, 1, i });
}
sort(qu.begin(), qu.end(), [](entry l, entry r) {
return l.i < r.i;
});
int cur = 0;
for (entry e : qu) {
while (cur <= e.i) {
for (int x : sw[cur]) {
//printf("Incrementing %d, %d\n", cur, x);
st1.seg_inc(x);
}
cur++;
}
ans[e.a] += e.f * st1.seg_sum(e.l, e.r);
}
for (int i = 0; i < M; i++) {
cout << ans[i] << "\n";
}
}
