#include <bits/stdc++.h>
using namespace std;
int n, q;
vector<string> S;
using sp = string::reverse_iterator;
int c[256];
int fcnt = 1, rcnt = 1;
struct fnode {
int l[4], mn, mx;
} fnd[2000005];
int fbuild(string &t, int x, bool add=true) {
int cur = 1;
for(auto &ch : t) {
if(add) {
if(!fnd[cur].mn) fnd[cur].mn = x;
fnd[cur].mx = x;
}
int &nxt = fnd[cur].l[c[int(ch)]];
if(!nxt) {
if(!add) return 0;
nxt = ++fcnt;
}
cur = nxt;
}
if(add) {
if(!fnd[cur].mn) fnd[cur].mn = x;
fnd[cur].mx = x;
}
return cur;
}
struct node {
static int cnt;
int l[4], v;
} nd[2000005];
int build(sp b, sp e, bool add=true, bool seg=false) {
int cur = 1;
for(; b != e; b++) {
if(seg) ++nd[cur].v;
int &nxt = nd[cur].l[c[int(*b)]];
if(!nxt) {
if(!add) return 0;
nxt = ++rcnt;
}
cur = nxt;
}
if(seg) ++nd[cur].v;
return cur;
}
int ans[2000005];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
c['A'] = 0; c['C'] = 1; c['G'] = 2; c['U'] = 3;
cin >> n >> q;
for(int i = 0; i < n; i++) {
string t;
cin >> t;
S.push_back(t);
}
sort(S.begin(), S.end());
// insert, plus, minus
// time, type, index (type: -1 : minus, 0 : update, 1 : plus)
vector<tuple<int, int, int>> que;
for(int i = 0; i < n; i++) {
fbuild(S[i], i+1);
int id = build(S[i].rbegin(), S[i].rend());
que.emplace_back(i, 0, id);
}
for(int i = 0; i < q; i++) {
string s, t;
cin >> s >> t;
int fid = fbuild(s, -1, false);
int rid = build(t.rbegin(), t.rend(), false);
if(!fid || !rid) continue;
int l = fnd[fid].mn, r = fnd[fid].mx;
--l; --r;
que.emplace_back(l, ~i, rid);
que.emplace_back(r, i+1, rid);
}
sort(que.begin(), que.end());
for(auto &[g, ty, id] : que) {
if(ty > 0) {
ans[ty-1] += nd[id].v;
} else if (ty < 0) {
ans[~ty] -= nd[id].v;
} else {
build(S[g].rbegin(), S[g].rend(), false, true);
}
}
for(int i = 0; i < q; i++) {
cout << ans[i] << '\n';
}
}
