#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=(int)2e5;
const int MAXLOG=18;
pair<string,int> s[N+2];
string q[N+2];
int num=0;
int n,m;
int lcp[2*N+2][MAXLOG+2],LOG[N*2+2];
bool cmp(pair<string,int>&x1,pair<string,int>&x2){
if (x1.first!=x2.first) return x1<x2;
return x1.second<x2.second;
}
LL ans[N+2];
int Getmn(int l,int r){
if (l>r) return 0;
int x=LOG[r-l+1];
return min(lcp[l][x],lcp[r-(1<<x)+1][x]);
}
struct Node{
int child[4]={};
int cnt=0;
Node(){
memset(child,-1,sizeof child);
cnt=0;
}
};
int type(char x){
if (x=='G') return 0;
if (x=='U') return 1;
if (x=='A') return 2;
if (x=='C') return 3;
}
class Trie{
public:
vector<Node>v;
void init(){
v.push_back(Node());
}
void add(string &x,int addmore){
int root=0;
for(int i=0;i<x.size();++i){
int c=type(x[i]);
if (v[root].child[c]==-1) v[root].child[c]=v.size(),v.push_back(Node());
v[root].cnt+=addmore;
root=v[root].child[c];
}
v[root].cnt+=addmore;
}
int Find(string&x){
int root=0;
for(int i=0;i<x.size();++i){
int c=type(x[i]);
if (v[root].child[c]==-1) return 0;
root=v[root].child[c];
}
return v[root].cnt;
}
};
Trie tree;
int Getlcp(int l,int r){
if (l>r) swap(l,r);
return Getmn(l+1,r);
}
const int BLOCKSIZE=447;
struct Mo_dtcl{
int l,r,id;
bool operator <(const Mo_dtcl&other) const{
if (l/BLOCKSIZE!=other.l/BLOCKSIZE){
return l/BLOCKSIZE<other.l/BLOCKSIZE;
}
return r<other.r;
}
};
vector<Mo_dtcl> qs;
int Lower(int id,int need){
int l=1,r=id-1,pos=id;
while (l<=r){
int m=(l+r)/2;
if (Getlcp(m,id)!=need) l=m+1;
else {
pos=m;
r=m-1;
}
}
return pos;
}
int Upper(int id,int need){
int l=id+1,r=num,pos=id;
while (l<=r){
int m=(l+r)/2;
if (Getlcp(id,m)!=need) r=m-1;
else {
pos=m;
l=m+1;
}
}
return pos;
}
void cong(int id,int val){
if (s[id].second==0) tree.add(s[id].first,val);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0) ; cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;++i){
string t; cin>>t;
s[++num]={t,0};
}
for(int i=1;i<=m;++i){
string t; cin>>t;
cin>>q[i];
reverse(q[i].begin(),q[i].end());
s[++num]={t,i};
}
sort(s+1,s+num+1,cmp);
lcp[1][0]=s[1].first.size();
for(int i=2;i<=num;++i){
for(int j=0;j<min(s[i-1].first.size(),s[i].first.size());++j){
if (s[i-1].first[j]!=s[i].first[j]) break;
lcp[i][0]++;
}
}
for(int i=2;i<=num;++i) LOG[i]=LOG[i/2]+1;
for(int j=1;j<=MAXLOG;++j){
for(int i=1;i+(1<<j)-1<=num;++i) {
lcp[i][j]=min(lcp[i][j-1],lcp[i+(1<<(j-1))][j-1]);
}
}
for(int i=1;i<=num;++i) reverse(s[i].first.begin(),s[i].first.end());
tree.init();
for(int i=1;i<=num;++i){
if (s[i].second!=0){
int l=Lower(i,s[i].first.size());
int r=Upper(i,s[i].first.size());
qs.push_back({l,r,s[i].second});
}
}
sort(qs.begin(),qs.end());
int l=1,r=0;
for(auto&x:qs){
while (l<x.l) cong(l++,-1);
while (l>x.l) cong(--l,1);
while (r<x.r) cong(++r,1);
while (r>x.r) cong(r--,-1);
ans[x.id]=tree.Find(q[x.id]);
}
for(int i=1;i<=m;++i) cout<<ans[i]<<'\n';
}
