#include<bits/stdc++.h>
using namespace std;
#define N 1<<23
int rts[N],ch1[N][4],ch2[N][4],mmpp[128],CC1,CC2,rt,sz[N],val[N],ans[200100];
bitset<N> hasaQ;
map<int,vector<pair<vector<int>,int>>> qrs;
int a_node(string str){
vector<int>v;
for(auto i:str)
v.push_back(mmpp[i]);
int k=rt;
for(auto i:v){
if(!ch1[k][i])
ch1[k][i]=++CC1;
k=ch1[k][i];
}
return k;
}
void Adtri2(int nod,string str,int b=1){
vector<int>v;
for(auto i:str)
v.push_back(mmpp[i]);
if(!rts[nod])
rts[nod]=++CC2;
int k=rts[nod];
sz[nod]+=str.size();
for(auto i:v){
if(!ch2[k][i])
ch2[k][i]=++CC2;
k=ch2[k][i],val[k]+=b;
}
sz[k]+=b;
}
int mrg(int a,int b){
if(!a||!b)return a+b;
if(sz[b]>sz[a])swap(a,b);
sz[a]+=sz[b],val[a]+=val[b];
for(int i=0;i<4;i++)
ch2[a][i]=mrg(ch2[a][i],ch2[b][i]);
return a;
}
int gothrough(int n,vector<int>v){
for(auto i:v)
n=ch2[n][i];
return n;
}
void do_a_dfs(int n){
if(!n)return;
for(auto k:ch1[n])
do_a_dfs(k),rts[n]=mrg(rts[n],rts[k]);
if(hasaQ[n]){
for(auto [x,y]:qrs[n])
ans[y]+=val[gothrough(rts[n],x)];
}
}
int main(){
mmpp['A']=0;
mmpp['C']=rt=CC1=1;
mmpp['G']=2;
mmpp['U']=3;
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
string str;
cin>>str;
int k=a_node(str);
reverse(str.begin(),str.end());
Adtri2(k,str);
}
for(int i=0;i<m;i++){
string a,b;
cin>>a>>b;
reverse(b.begin(),b.end());
int k=a_node(a);
vector<int>v;
for(auto i:b)
v.push_back(mmpp[i]);
hasaQ[k]=1;
qrs[k].push_back({v,i});
}
for(int x=CC2;x;x--) {
sz[x]=1;
for(auto k:ch2[x])
sz[x]+=sz[k];
}
do_a_dfs(rt);
for(int i=0;i<m;i++)
cout<<ans[i]<<'\n';
}
