#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
struct B{int n;vi t;B(int n):n(n),t(n+1){};void u(int i){for(;i<=n;i+=i&-i)t[i]++;}int q(int i){int s=0;for(;i>0;i-=i&-i)s+=t[i];return s;}int qr(int l,int r){return q(r)-q(l-1);}};
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n,m;cin>>n>>m;
vector<string>s(n);
for(int i=0;i<n;i++)cin>>s[i];
vector<string>p(m),q(m);
for(int i=0;i<m;i++)cin>>p[i]>>q[i];
int c1=1;
vector<array<int,4>>ch1(2000005);
vi tin1(2000005),tout1(2000005);
for(int i=0;i<2000005;i++)for(int j=0;j<4;j++)ch1[i][j]=0;
for(auto&x:s){
int u=1;
for(char cc:x){
int v=(cc=='A'?0:cc=='G'?1:cc=='C'?2:3);
if(!ch1[u][v])ch1[u][v]=++c1;
u=ch1[u][v];
}
}
int t1=0;
vector<vector<int>>e1(c1+1);
for(int u=1;u<=c1;u++)for(int v=0;v<4;v++)if(ch1[u][v])e1[u].push_back(ch1[u][v]);
function<void(int)>d1=[&](int u){
tin1[u]=++t1;
for(int v:e1[u])d1(v);
tout1[u]=t1;
};
d1(1);
int c2=1;
vector<array<int,4>>ch2(2000005);
vi tin2(2000005),tout2(2000005);
for(int i=0;i<2000005;i++)for(int j=0;j<4;j++)ch2[i][j]=0;
for(auto&x:s){
int u=1;
for(int i=x.size()-1;i>=0;i--){
char cc=x[i];
int v=(cc=='A'?0:cc=='G'?1:cc=='C'?2:3);
if(!ch2[u][v])ch2[u][v]=++c2;
u=ch2[u][v];
}
}
int t2=0;
vector<vector<int>>e2(c2+1);
for(int u=1;u<=c2;u++)for(int v=0;v<4;v++)if(ch2[u][v])e2[u].push_back(ch2[u][v]);
function<void(int)>d2=[&](int u){
tin2[u]=++t2;
for(int v:e2[u])d2(v);
tout2[u]=t2;
};
d2(1);
vector<pair<int,int>>pts(n);
for(int i=0;i<n;i++){
int u=1;
for(char cc:s[i]){
int v=(cc=='A'?0:cc=='G'?1:cc=='C'?2:3);
u=ch1[u][v];
}
int x=tin1[u];
u=1;
for(int i2=s[i].size()-1;i2>=0;i2--){
char cc=s[i][i2];
int v=(cc=='A'?0:cc=='G'?1:cc=='C'?2:3);
u=ch2[u][v];
}
int y=tin2[u];
pts[i]={x,y};
}
struct Q{int x,l,r,i,sg;};
vector<Q>qs;
for(int i=0;i<m;i++){
int u=1;
bool ok=true;
for(char cc:p[i]){
int v=(cc=='A'?0:cc=='G'?1:cc=='C'?2:3);
if(!ch1[u][v]){ok=false;break;}
u=ch1[u][v];
}
int l1,r1;
if(!ok)l1=1,r1=0;
else l1=tin1[u],r1=tout1[u];
u=1;ok=true;
for(int j2=q[i].size()-1;j2>=0;j2--){
char cc=q[i][j2];
int v=(cc=='A'?0:cc=='G'?1:cc=='C'?2:3);
if(!ch2[u][v]){ok=false;break;}
u=ch2[u][v];
}
int l2,r2;
if(!ok)l2=1,r2=0;
else l2=tin2[u],r2=tout2[u];
if(l1>r1||l2>r2)continue;
qs.push_back({r1,l2,r2,i,1});
qs.push_back({l1-1,l2,r2,i,-1});
}
sort(pts.begin(),pts.end());
sort(qs.begin(),qs.end(),[](auto &a,auto &b){return a.x<b.x;});
B bit(t2);
vi ans(m);
int pi=0;
for(auto &qv:qs){
while(pi<n&&pts[pi].first<=qv.x){
bit.u(pts[pi].second);
pi++;
}
ans[qv.i]+=qv.sg*bit.qr(qv.l,qv.r);
}
for(int i=0;i<m;i++)cout<<ans[i]<<"\n";
return 0;
}
