#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xx first
#define yy second
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,int) sort(a.begin(),a.end(),greater<int>())
#define lb(a,x) lower_bound(a.begin(),a.end(),x)
#define up(a,x) upper_bound(a.begin(),a.end(),x)
#define fnd(a,x) find(a.begin(),a.end(),x)
#define vstart auto startt=chrono::system_clock::now()
#define vend auto endd=chrono::system_clock::now()
#define vvreme chrono::duration<double> vremee=endd-startt
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef string str;
const int maxn=1e5+10;
const int maxa=2e6+10;
const int pp=31;
const int mod=1e9+7;
str niz[maxn];
int novi[maxa];
pii kad[maxn];
int koliko=0;
int koji[256];
vector<int> tree[4*maxa+50];
int mul(ll a,ll b){
if(a*b>=mod) return a*b%mod;
return a*b;
}
int add(ll a,ll b){
if(a+b>=mod) return (a+b)%mod;
return a+b;
}
int sta(int mid,str &p){
if(p.size()>niz[mid].size()){
return (p<niz[mid] ? 3:1);
}
for(int i=0;i<min(p.size(),niz[mid].size());i++){
if(p[i]<niz[mid][i]) return 3;
if(p[i]>niz[mid][i]) return 1;
}
return 2;
}
pii range(str &p,int n){
int l=0;
int r=n-1;
int prvi=-1;
while(l<=r){
int mid=l+(r-l)/2;
int odg=sta(mid,p);
if(odg==1){
l=mid+1;
}else if(odg==2){
r=mid-1;
prvi=mid;
}else r=mid-1;
}
l=0;
r=n-1;
int drugi=-1;
while(l<=r){
int mid=l+(r-l)/2;
int odg=sta(mid,p);
if(odg==1){
l=mid+1;
}else if(odg==2){
l=mid+1;
drugi=mid;
}else r=mid-1;
}
if(prvi==-1 || drugi==-1) return {-1,-1};
return {kad[prvi].xx,kad[drugi].yy};
}
void spoji(vector<int> &a,vector<int> &b,vector<int> &res){
res.resize(a.size()+b.size());
int tren=0;
int i=0;
int j=0;
while(i<a.size() || j<b.size()){
res[tren]=INT_MAX;
if(i<a.size()) res[tren]=min(res[tren],a[i]);
if(j<b.size()) res[tren]=min(res[tren],b[j]);
if(i<a.size() && a[i]==res[tren]) i++;
else if(j<b.size() && b[j]==res[tren]) j++;
tren++;
}
}
void build(int ind,int l,int r){
if(l==r){
tree[ind]={novi[l]};
return;
}
int mid=l+(r-l)/2;
build(2*ind,l,mid);
build(2*ind+1,mid+1,r);
spoji(tree[2*ind],tree[2*ind+1],tree[ind]);
}
int query(int ind,int l,int r,int tl,int tr,int v){
if(l==r){
return int(novi[l]==v);
}
if(tl<=l && r<=tr){
return upper_bound(tree[ind].begin(),tree[ind].end(),v)-lower_bound(tree[ind].begin(),tree[ind].end(),v);
}
int mid=l+(r-l)/2;
int ret=0;
if(tl<=mid) ret+=query(2*ind,l,mid,tl,tr,v);
if(tr>mid) ret+=query(2*ind+1,mid+1,r,tl,tr,v);
return ret;
}
void solve(){
koji['A']=1;
koji['G']=2;
koji['C']=3;
koji['U']=4;
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++) cin>>niz[i];
sort(niz,niz+n);
for(int i=0;i<n;i++){
int hsh=0;
kad[i].xx=koliko;
for(int j=niz[i].size()-1;j>=0;j--){
hsh=mul(hsh,pp);
hsh=add(hsh,mul(pp,koji[niz[i][j]]));
novi[koliko++]=hsh;
}
kad[i].yy=koliko-1;
}
build(1,0,koliko-1);
while(m--){
str p,q;
cin>>p>>q;
pii pom=range(p,n);
if(pom.xx==-1 || pom.yy==-1){cout<<0<<"\n"; continue;}
int hsh=0;
for(int j=q.size()-1;j>=0;j--){
hsh=mul(hsh,pp);
hsh=add(hsh,mul(pp,koji[q[j]]));
}
cout<<query(1,0,koliko-1,pom.xx,pom.yy,hsh)<<"\n";
}
}
int main(){
ios;
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
