#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define ff first
#define ss second
#define pb push_back
#define vi vector<int>
#define fr(i,ii,iii) for(int i=ii;i<iii;i++)
const int M=2e6+5;
int n,m;
string a[M];
map<char,int>mp={{'A',0},{'G',1},{'C',2},{'U',3}};
int trie[M][4][2],ct[2],id,idx,f[M][2];
pii p[M];
/*
id - prefix tu sufix trie
idx - indexi stringis
ct - tries gadanomrva
t1 - timer
f - am wveroze romeli sityva damtavrda
p - koordinatebi
*/
int in[M][2],out[M][2],t1;
struct qry{
int tp,xx,yy,yy1,ind;
bool operator<(const qry&oth)const{
if(xx==oth.xx)return tp<oth.tp;
return xx<oth.xx;
}
};
vector<qry>v;
int ans[M];
void ins(string s){
int st=0;
for(auto i:s){
int &x=trie[st][mp[i]][id];
if(x==0)x=++ct[id];
st=x;
}
if(f[st][id]==0)f[st][id]=idx;
}
void dfs(int st){
t1++;
in[st][id]=t1;
if(f[st][id]){
if(id==0)p[f[st][id]].ff=t1;
else p[f[st][id]].ss=t1;
}
fr(i,0,4){
int x=trie[st][i][id];
if(x!=0)dfs(x);
}
out[st][id]=t1;
}
pii fnd(string x){
int st=0;
for(auto i:x){
if(trie[st][mp[i]][id]==0){
return{-1,-1};
}
st=trie[st][mp[i]][id];
}
return{in[st][id],out[st][id]};
}
int fenw[2*M];
void addfenw(int x,int val){
while(x<=2e6){
fenw[x]+=val;
x+= x & -x;
}
}
int getfenw(int x){
int s=0;
while(x>=1){
s+=fenw[x];
x-= x & -x;
}
return s;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin>>n>>m;
fr(i,1,n+1){
cin>>a[i];
reverse(a[i].begin(),a[i].end());
idx=i;
id=1;ins(a[i]);
reverse(a[i].begin(),a[i].end());
id=0;ins(a[i]);
}
t1=-1;id=0;dfs(0);
t1=-1;id=1;dfs(0);
map<string,int>mp;
fr(i,1,n+1){
if(mp.count(a[i])){
v.pb(v[mp[a[i]]]);
continue;
}
v.pb({0,p[i].ff,p[i].ss,p[i].ss,-1});
mp[a[i]]=v.size()-1;
}
fr(i,1,m+1){
string aa,bb;cin>>aa>>bb;reverse(bb.begin(),bb.end());
id=0;pii p1=fnd(aa);//pr
id=1;pii p2=fnd(bb);//sf
if(p1.ff==-1 or p2.ff==-1){
continue;
}
v.pb({1,p1.ff-1,p2.ff,p2.ss,i});
v.pb({2,p1.ss,p2.ff,p2.ss,i});
}
sort(v.begin(),v.end());
for(auto i:v){
if(i.tp==0){
addfenw(i.yy,1);
}
else if(i.tp==1){
ans[i.ind]-=getfenw(i.yy1)-getfenw(i.yy-1);
}
else{
ans[i.ind]+=getfenw(i.yy1)-getfenw(i.yy-1);
}
}
fr(i,1,m+1){
cout<<ans[i];
if(i!=m)cout<<"\n";
}
}
/*
4 5
AUUUUU
GCGCG
AUGC
AAAA
G G
AAA AAA
AAAA AAAA
AAAA AAAAA
AUUUUU UUUU
*/
