#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;
const int N = 1e5+1;
int id = 0;
struct Node {
int v = 0;
vector<int> ids;
vector<int> qshere;
int trieroot;
int c[4];
Node() {
c[0] = c[1] = c[2] = c[3] = trieroot = -1;
};
};
vector<Node> nds;
int newnode() {
nds.push_back(Node());
return id++;
}
vector<string> strs(N),rev(N);
vector<pair<string,string>> qs(N);
vi ans(N);
void ins(int node,int id,const string& s,int qry = 0,int dep = 0) {
//cerr << node sp id sp s sp qry sp dep << endl;
nds[node].v++;
if (dep == big(s)) {
if (!qry) nds[node].ids.push_back(id);
else if (qry == 1) nds[node].qshere.push_back(id);
return;
}
char togo = s[dep];
if (nds[node].c[togo-'A'] == -1) {
nds[node].c[togo-'A'] = newnode();
//cerr << "CHILD OF" sp node sp togo sp "BECAME " << nds[node].c[togo-'A'] << endl;
}
ins(nds[node].c[togo-'A'],id,s,qry,dep+1);
}
int query(int node,const string& s,int dep = 0) {
//cerr << node sp s sp dep sp nds[node].v << endl;
if (dep == big(s)) {
return nds[node].v;
}
int togo = s[dep];
if (nds[node].c[togo-'A'] == -1) return 0;
return query(nds[node].c[togo-'A'],s,dep+1);
}
void walk(int node) {
for (auto it : nds[node].ids) {
if (nds[node].trieroot == -1) {
nds[node].trieroot = newnode();
//cerr << "ROOT OF" sp node sp "BECAME" sp nds[node].trieroot << endl;
}
ins(nds[node].trieroot,it,rev[it],2,0);
}
for (int i = 0;i<4;i++) {
if (nds[node].c[i] == -1) continue;
int it = nds[node].c[i];
walk(nds[node].c[i]);
if (big(nds[node].ids) < big(nds[it].ids)) {
nds[node].ids.swap(nds[it].ids);
swap(nds[node].trieroot,nds[it].trieroot);
}
for (auto id : nds[it].ids) {
if (nds[node].trieroot == -1) {
nds[node].trieroot = newnode();
//cerr << "ROOT OF" sp node sp "BECAME" sp nds[node].trieroot << endl;
}
ins(nds[node].trieroot,id,rev[id],2,0);
nds[node].ids.push_back(id);
}
}
for (auto it : nds[node].qshere) {
if (nds[node].trieroot == -1) {
ans[it] = 0;
continue;
}
int qq = query(nds[node].trieroot,qs[it].second);
//cout << node sp it sp qq << endl;
ans[it] = qq;
}
}
void solve() {
int n,q;
cin >> n >> q;
for (int i=1;i<=n;i++) {
cin >> strs[i];
for (auto& c : strs[i]) {
if (c == 'A' || c == 'C') continue;
if (c == 'G') c = 'B';
else c = 'D';
}
rev[i] = strs[i];
reverse(all(rev[i]));
}
//for (int i=1;i<=n;i++) cout << strs[i] << endl;
int root = newnode();
for (int i=1;i<=n;i++) ins(root,i,strs[i]);
for (int i = 1;i<=q;i++) {
cin >> qs[i].ff >> qs[i].ss;
reverse(all(qs[i].ss));
for (auto& c : qs[i].ff) {
if (c == 'A' || c == 'C') continue;
if (c == 'G') c = 'B';
else c = 'D';
}
for (auto& c : qs[i].ss) {
if (c == 'A' || c == 'C') continue;
if (c == 'G') c = 'B';
else c = 'D';
}
//cout << qs[i].ff sp qs[i].ss << endl;
ins(root,i,qs[i].ff,1,0);
}
walk(root);
for (int i=1;i<=q;i++) cout << ans[i] << '\n';
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef Dodi
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int t = 1;
//cin >> t;
while (t --> 0) solve();
}
