#include <bits/stdc++.h>
using namespace std;
const int lenmax = 2e6 + 5, nmax = 1e5 + 5;
int n, q;
int encr[256], decr[256];
string pad;
struct Trie {
Trie* v[4] = {0, 0, 0, 0};
vector<int> list;
int l, r;
void insert(int *s, int val) {
l = 0, r = 0;
if(s[0] == -1) {
list.push_back(val);
return;
}
if(v[s[0]] == 0)
v[s[0]] = new Trie;
v[s[0]]->insert(s + 1, val);
return;
}
void construct(vector<int>& preord) {
l = preord.size();
for(auto x : list)
preord.push_back(x);
for(int i = 0; i < 4; i++) {
if(v[i] != 0)
v[i]->construct(preord);
}
r = preord.size() - 1;
}
pair<int,int> query(int *s) {
if(s[0] == -1) {
return {l, r};
}
if(v[s[0]] == 0)
return {-1, -1};
return v[s[0]]->query(s + 1);
}
} forw, back;
int s[lenmax];
static void init() {
encr['A'] = 0;
encr['C'] = 1;
encr['G'] = 2;
encr['U'] = 3;
encr['\n'] = -1;
decr[0] = 'A';
decr[1] = 'C';
decr[2] = 'G';
decr[3] = 'U';
}
namespace AINT {
int aint[nmax * 4];
void add(int poz, int node = 1, int cl = 0, int cr = n - 1) {
if(cl == cr) {
aint[node]++;
return;
}
int mid = cl + cr >> 1;
if(poz <= mid)
add(poz, 2 * node, cl, mid);
else
add(poz, 2 * node + 1, mid + 1, cr);
aint[node] = aint[node * 2 + 1] + aint[node * 2];
}
int query(int l, int r, int node = 1, int cl = 0, int cr = n - 1) {
if(cr < l || r < cl)
return 0;
if(l <= cl && cr <= r)
return aint[node];
int mid = cl + cr >> 1;
return query(l, r, 2 * node, cl, mid) + query(l, r, 2 * node + 1, mid + 1, cr);
}
}
int rez[nmax];
vector<tuple<int,int,int> > qs[nmax];
#define qs (qs + 1)
int main() {
init();
cin >> n >> q;
cin.get();
for(int i = 0, ptr = 0; i < n; ptr = 0, i++) {
char ch;
while((ch = cin.get()) != '\n') {
s[ptr++] = encr[ch];
}
s[ptr] = -1;
forw.insert(s, i);
reverse(s, s + ptr);
back.insert(s, i);
}
vector<int> fata, spate, inv;
forw.construct(fata);
back.construct(spate);
assert(fata.size() == n);
assert(spate.size() == n);
inv.resize(spate.size());
//for(auto x : fata)
//cout << x << ' ';
//cout << '\n';
//for(auto x : spate)
//cout << x << ' ';
//cout << '\n';
for(int i = 0; i < spate.size(); i++)
inv[spate[i]] = i;
for(int i = 0; i < fata.size(); i++)
fata[i] = inv[fata[i]];
//for(auto x : fata)
//cout << x << ' ';
//cout << '\n';
for(int i = 1, ptr = 0, l1, r1, l2, r2; i <= q; ptr = 0, i++) {
char ch;
while(!isspace(ch = cin.get())) {
s[ptr++] = encr[ch];
}
s[ptr] = -1;
ptr = 0;
tie(l1, r1) = forw.query(s);
while(!isspace(ch = cin.get())) {
s[ptr++] = encr[ch];
}
s[ptr] = -1;
reverse(s, s + ptr);
tie(l2, r2) = back.query(s);
if(l1 >= 0 && l2 >= 0 && r1 >= 0 && r2 >= 0) {
qs[l1 - 1].push_back({-i, l2, r2});
qs[r1].push_back({i, l2, r2});
}
//cerr << l1 << ' ' << r1 << ' '<< l2 << ' ' << r2 << '\n';
}
for(int i = 0; i < fata.size(); i++) {
AINT::add(fata[i]);
for(auto [ind, l, r] : qs[i])
rez[abs(ind)] += AINT::query(l, r) * (ind / abs(ind));
}
for(int i = 1; i <= q; i++)
cout << rez[i] << '\n';
}
