#include <bits/stdc++.h>
using namespace std; using ll = long long; const int N = 100005;
int I[300], inf = 1e9;
struct pre {
pre* child[4]; int MAX, MIN;
pre() { for(int i=0;i<4;++i) child[i] = nullptr ; MIN = inf; MAX = 0;}
} root;
struct suf {
suf* child[4]; vector<int> ID; bool ok;
suf() {for(int i=0;i<4;++i) child[i] = nullptr; ok = 0; }
} ROOT;
void add(string s, int id) {
pre* p = &root;
for(char c : s) {
if(p->child[I[c]] == nullptr) p->child[I[c]] = new pre();
p = p->child[I[c]];
p->MIN = min(p->MIN, id);
p->MAX = max(p->MAX, id);
}
suf* P = &ROOT;
for(int i=s.length()-1;i>=0;--i) {
if(P->child[I[s[i]]] == nullptr) P->child[I[s[i]]] = new suf();
P = P->child[I[s[i]]];
P->ID.push_back(id);
}
}
pair<int,int> query(string s) {
pre* p = &root;
for(char c : s) {
if(p->child[I[c]] == nullptr) return make_pair(inf,inf);
p = p->child[I[c]];
}
return make_pair(p->MIN, p->MAX);
}
int get(string s, int L, int R) {
reverse(s.begin(), s.end());
suf* P = &ROOT;
for(char c : s) {
if(P->child[I[c]] == nullptr) return 0;
P = P->child[I[c]];
}
if(!P->ok) sort(P->ID.begin(), P->ID.end()), P->ok = 1;
int res = upper_bound(P->ID.begin(), P->ID.end(), R) - lower_bound(P->ID.begin(), P->ID.end(), L);
return max(res, 0);
}
string s[N];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
I['A'] = 0;
I['U'] = 1;
I['G'] = 2;
I['C'] = 3;
int n, m;
cin >> n >> m;
for(int i=1;i<=n;++i) cin >> s[i];
sort(s+1,s+n+1);
for(int i=1;i<=n;++i) add(s[i], i);
while(m--) {
string p, q;
cin >> p >> q;
pair<int,int> lim = query(p);
cout << get(q, lim.first, lim.second) << '\n';
}
return 0;
}
