#include <bits/stdc++.h>
#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;
vector<vector<int>> ids,qshere;
vector<int> trieroot,v;
vector<array<int,4>> c;
int newnode() {
trieroot.push_back(-1);
v.push_back(0);
c.push_back({-1,-1,-1,-1});
ids.push_back({});
qshere.push_back({});
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,int dep) {
v[node]++;
if (dep == big(s)) {
if (!qry) ids[node].push_back(id);
else if (qry == 1) qshere[node].push_back(id);
return;
}
char togo = s[dep];
if (c[node][togo-'A'] == -1) c[node][togo-'A'] = newnode();
ins(c[node][togo-'A'],id,s,qry,dep+1);
}
int query(int node,const string& s,int dep) {
if (dep == big(s)) return v[node];
int togo = s[dep];
if (c[node][togo-'A'] == -1) return 0;
return query(c[node][togo-'A'],s,dep+1);
}
void walk(int node) {
for (auto it : ids[node]) {
if (trieroot[node] == -1) trieroot[node] = newnode();
ins(trieroot[node],it,rev[it],2,0);
}
for (int i = 0;i<4;i++) {
if (c[node][i] == -1) continue;
int it = c[node][i];
walk(c[node][i]);
if (big(ids[node]) < big(ids[it])) {
ids[node].swap(ids[it]);
swap(trieroot[node],trieroot[it]);
}
for (auto id : ids[it]) {
if (trieroot[node] == -1) trieroot[node] = newnode();
ins(trieroot[node],id,rev[id],2,0);
ids[node].push_back(id);
}
ids[it].clear();
}
for (auto it : qshere[node]) {
if (trieroot[node] == -1) {
ans[it] = 0;
continue;
}
int qq = query(trieroot[node],qs[it].second,0);
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]));
}
int root = newnode();
for (int i=1;i<=n;i++) ins(root,i,strs[i],0,0);
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';
}
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();
}
