#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
const int MAXN = 100000;
const int BLOCK = 300;
int n, m;
int P[200];
int pre_arr[MAXN+1];
int suf_arr[MAXN+1];
pii pre_ran[MAXN+1];
pii suf_ran[MAXN+1];
int pos[MAXN+1];
int ans[MAXN];
string s, p, q;
int cc;
struct Qry{
int l, r, id;
Qry() {}
Qry(int _l, int _r, int _id) {
l = _l, r = _r, id = _id;
}
} qry[MAXN];
class Trie{
private:
struct node{
int c[4];
vector <int> id;
int l, r;
} arr[MAXN*20+1];
int cnt;
public:
void add(string &s, int id) {
int now = 0;
for (int i = 0; i < s.size(); i++) {
if (!arr[now].c[P[s[i]]])
arr[now].c[P[s[i]]] = ++cnt;
now = arr[now].c[P[s[i]]];
}
arr[now].id.pb(id);
}
void dfs(int now, int A[]) {
arr[now].l = cc+1;
for (int i = 0; i < 4; i++) {
if (!arr[now].c[i]) continue;
dfs(arr[now].c[i], A);
}
for (int i : arr[now].id)
A[++cc] = i;
arr[now].r = cc;
}
void tag(string &s, int id, pii A[]) {
int now = 0;
for (int i = 0; i < s.size(); i++) {
if (!arr[now].c[P[s[i]]]) {
now = 0;
break;
}
now = arr[now].c[P[s[i]]];
}
if (now)
A[id] = pii(arr[now].l, arr[now].r);
}
} pre, suf;
class Seg{
private:
int arr[MAXN*4+1];
void pull(int now) {
arr[now] = arr[now*2] + arr[now*2+1];
}
public:
void mdy(int p, int v, int now=1, int l=1, int r=n) {
if (l == p && r == p) {
arr[now] += v;
return;
} else if (l > p || r < p) return;
int mid = l + r >> 1;
mdy(p, v, now*2 , l, mid);
mdy(p, v, now*2+1,mid+1,r);
pull(now);
}
int qry(int ql, int qr, int now=1, int l=1, int r=n) {
if (ql <= l && r <= qr) {
return arr[now];
} else if (l > qr || r < ql) return 0;
int mid = l + r >> 1, sum = 0;
sum += qry(ql, qr, now*2 , l, mid);
sum += qry(ql, qr, now*2+1,mid+1,r);
return sum;
}
} seg;
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0);
P['A'] = 0, P['U'] = 1, P['C'] = 2, P['G'] = 3;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> s;
pre.add(s, i);
reverse(s.begin(), s.end());
suf.add(s, i);
}
cc = 0;
pre.dfs(0, pre_arr);
cc = 0;
suf.dfs(0, suf_arr);
int tmp[MAXN+1];
for (int i = 1; i <= n; i++)
tmp[pre_arr[i]] = i;
for (int i = 1; i <= n; i++)
suf_arr[i] = tmp[suf_arr[i]];
for (int i = 1; i <= m; i++) {
cin >> p >> q;
pre.tag(p, i, pre_ran);
reverse(q.begin(), q.end());
suf.tag(q, i, suf_ran);
qry[i-1] = Qry(suf_ran[i].ff, suf_ran[i].ss, i);
}
sort(qry, qry+m, [](const Qry a, const Qry b) {
return (a.l / BLOCK != b.l / BLOCK) ? a.l < b.l : a.r < b.r;
});
int nowL = 1, nowR = 0;
for (int i = 0; i < m; i++) {
int id = qry[i].id;
while (nowR < qry[i].r)
seg.mdy(suf_arr[++nowR], 1);
while (nowL > qry[i].l)
seg.mdy(suf_arr[--nowL], 1);
while (nowR > qry[i].r)
seg.mdy(suf_arr[nowR--], -1);
while (nowL < qry[i].l)
seg.mdy(suf_arr[nowL++], -1);
ans[id] = seg.qry(pre_ran[id].ff, pre_ran[id].ss);
}
for (int i = 1; i <= m; i++)
cout << ans[i] << '\n';
return 0;
}
