#include <bits/stdc++.h>
using namespace std;
#define exe cerr<<1.0*clock()/CLOCKS_PER_SEC;
#define io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define iof(file) freopen(file ".inp","r",stdin);freopen(file ".out","w",stdout);
#define ll long long
#define eb emplace_back
#define T tuple<int,int,int>
#define P pair<int,int>
const ll N=1e5+5,lim=1e7,mod=1e9+7;
int n,m;
string a[N];
int f(char x){
if (x=='A') return 0;
else if (x=='U') return 1;
else if (x=='G') return 2;
return 3;
}
struct trie{
struct node{
node* child[4];
vector<int> ans;
int l,r;
node(){
l=0;
r=0;
memset(child,0,sizeof child);
}
};
node* root = new node();
void upd1(string s,int idx){
node* id=root;
for (char i:s){
int k=f(i);
if (!id->child[k]){
id->child[k] = new node();
id=id->child[k];
id->l=idx;
id->r=idx;
}
else{
id=id->child[k];
id->r=idx;
}
}
}
void upd2(string s,int idx){
node* id=root;
for (char i:s){
int k=f(i);
if (!id->child[k]) id->child[k] = new node();
id=id->child[k];
id->ans.eb(idx);
}
}
P get1(string s){
node* id=root;
for (char i:s){
int k=f(i);
if (!id->child[k]) return {0,0};
id=id->child[k];
}
return {id->l,id->r};
}
int get2(string s,P lim){
node* id=root;
for (char i:s){
int k=f(i);
if (!id->child[k]) return 0;
id=id->child[k];
}
return upper_bound(id->ans.begin(),id->ans.end(),lim.second)-
lower_bound(id->ans.begin(),id->ans.end(),lim.first);
}
} trie1,trie2;
int main(){
io
// iof("io")
cin>>n>>m;
for (int i=1;i<=n;++i) cin>>a[i];
sort(a+1,a+n+1);
for (int i=1;i<=n;++i){
trie1.upd1(a[i],i);
reverse(a[i].begin(),a[i].end());
trie2.upd2(a[i],i);
}
for (int i=1;i<=m;++i){
string p,q; cin>>p>>q;
reverse(q.begin(),q.end());
P lim=trie1.get1(p);
cout<<trie2.get2(q,lim)<<'\n';
}
exe
return 0;
}
