#include <bits/stdc++.h>
using namespace std;
int ans[100005];
int func(char x) {
return (x == 'A' ? 0 : (x == 'G' ? 1 : (x == 'C' ? 2 : 3)));
}
struct node {
int cnt = 0, sz=0;
node* ptr[4] = {};
vector<pair<string, int>> qrs;
node* root;
} *root;
int n, q;
string str[100005];
string a, b;
void insa(node*&cur, string& toins, int idx, bool mode = 1) {
if(!cur) cur = new node();
cur->cnt++; cur->sz += toins.size();
if(idx != toins.size()) {
insa(cur->ptr[func(toins[idx])], toins, idx+1, mode);
} else if(mode) {
string &revver = toins;
reverse(revver.begin(), revver.end());
insa(cur->root, revver, 0, 0);
}
}
string curs = "";
void traverse(node *&cur) {
if(cur) cout << curs << '\n';
else return ;
for(int i=0;i<4;i++) {
curs += 'A' + i;
traverse(cur->ptr[i]);
curs.pop_back();
}
} //bruh
void marknode(node *&cur, string &a, string &b, int qridx, int idx) {
if(!cur) return;
if(idx == a.size()) {
cur->qrs.emplace_back(b, qridx);
} else marknode(cur->ptr[func(a[idx])], a, b, qridx, idx+1);
}
int match(node *&cur, string &a, int idx) {
if(!cur) return 0;
if(idx == a.size()) {return cur->cnt;}
return match(cur->ptr[func(a[idx])], a, idx+1);
}
void mg(node *&added, node *&adder) {
if(!adder) return;
if(!added) {added = adder; return;}
added->cnt += adder ->cnt;
added->sz += adder->sz;
for(int i=0;i<4;i++) mg(added->ptr[i], adder->ptr[i]);
}
int getsz(node *a) {
return a ? a->sz : 0;
}
void dfsans(node *&cur) {
if(!cur) return;
for(int i=0;i<4;i++) {
dfsans(cur->ptr[i]);
if(cur->ptr[i]) {
if(getsz(cur->root) < getsz(cur->ptr[i]->root)) swap(cur->ptr[i]->root, cur->root);
}
}
for(int i=0;i<4;i++) {
if(cur->ptr[i])
mg(cur->root, cur->ptr[i]->root);
}
for(auto &e:cur->qrs) {
ans[e.second] = match(cur->root, e.first, 0);
}
}
int main() {
cin.tie(0) -> sync_with_stdio(0);
cin >> n >> q;
for(int i=0;i<n;i++) {
cin >> str[i];
insa(root, str[i], 0);
}
for(int i=0;i<q;i++) {
cin >> a >> b; reverse(b.begin(), b.end());
marknode(root, a, b, i, 0);
}
dfsans(root);
for(int i=0;i<q;i++) cout << ans[i] << '\n';
}
