#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <map>
using namespace std;
struct A
{
int nxt[5];
int con=0;
int len;
int l,r;
}Node[5][2000005];
struct B
{
int l,r;
int nxl,nxr;
int nxt;
int con;
}Node2[20000005];
vector < vector < int > > all[5];
vector < int > xx[5];
pair < int , int > where[100005];
char ttt[100005];
int sz[100005];
int cha[505];
int now[5]={1,1};
int tt[5]={0,0};
int now2=1,N;
int con;
void New(int x,int y,int z)
{
Node[x][y].con=0;
Node[x][y].nxt[0]=-1;
Node[x][y].nxt[1]=-1;
Node[x][y].nxt[2]=-1;
Node[x][y].nxt[3]=-1;
Node[x][y].len=z;
}
void build(int x,int y,int here)
{
if(Node[x][here].len==sz[y])
{
Node[x][here].con++;
return;
}
if(Node[x][here].nxt[all[x][y][Node[x][here].len]]==-1)
{
Node[x][here].nxt[all[x][y][Node[x][here].len]]=now[x]++;
New(x,Node[x][here].nxt[all[x][y][Node[x][here].len]],Node[x][here].len+1);
}
build(x,y,Node[x][here].nxt[all[x][y][Node[x][here].len]]);
}
void BFS(int x,int here)
{
int i;
Node[x][here].l=tt[x];
Node[x][here].r=tt[x]+Node[x][here].con-1;
tt[x]+=Node[x][here].con;
for(i=0;i<4;i++)
{
if(Node[x][here].nxt[i]!=-1)
{
BFS(x,Node[x][here].nxt[i]);
Node[x][here].r=Node[x][Node[x][here].nxt[i]].r;
}
}
}
pair < int , int > Find(int x,int here)
{
if(Node[x][here].len==con) return make_pair(Node[x][here].l,Node[x][here].r);
if(Node[x][here].nxt[xx[0][Node[x][here].len]]==-1) return make_pair(-1,-1);
return Find(x,Node[x][here].nxt[xx[0][Node[x][here].len]]);
}
void New2(int l,int r,int nxt,int here)
{
Node2[here].l=l;
Node2[here].r=r;
Node2[here].nxt=nxt;
Node2[here].nxl=-1;
Node2[here].nxr=-1;
Node2[here].con=0;
}
void add(int x,int y,int here)
{
//printf("%d %d %d %d %d %d\n",x,y,here,Node2[here].l,Node2[here].r,Node2[here].nxt);
Node2[here].con++;
if(Node2[here].nxt==-2)
{
if(y==Node2[here].l&&y==Node2[here].r) return ;
if(y<=(Node2[here].l+Node2[here].r)/2)
{
if(Node2[here].nxl==-1)
{
Node2[here].nxl=now2++;
New2(Node2[here].l,(Node2[here].l+Node2[here].r)/2,-2,Node2[here].nxl);
}
add(x,y,Node2[here].nxl);
}
else
{
if(Node2[here].nxr==-1)
{
Node2[here].nxr=now2++;
New2((Node2[here].l+Node2[here].r)/2+1,Node2[here].r,-2,Node2[here].nxr);
}
add(x,y,Node2[here].nxr);
}
}
else
{
if(Node2[here].nxt==-1)
{
Node2[here].nxt=now2++;
New2(0,N,-2,Node2[here].nxt);
}
add(x,y,Node2[here].nxt);
if(x==Node2[here].l&&x==Node2[here].r) return;
if(x<=(Node2[here].l+Node2[here].r)/2)
{
if(Node2[here].nxl==-1)
{
Node2[here].nxl=now2++;
New2(Node2[here].l,(Node2[here].l+Node2[here].r)/2,-1,Node2[here].nxl);
}
add(x,y,Node2[here].nxl);
}
else
{
if(Node2[here].nxr==-1)
{
Node2[here].nxr=now2++;
New2((Node2[here].l+Node2[here].r)/2+1,Node2[here].r,-1,Node2[here].nxr);
}
add(x,y,Node2[here].nxr);
}
}
}
int main()
{
pair < int , int > a,b;
int M,K,t=0,i,j,k,t2,ans=0;
cha['A']=0;
cha['U']=1;
cha['C']=2;
cha['G']=3;
scanf("%d %d",&N,&M);
New2(0,N,-1,0);
New(0,0,0);
New(1,0,0);
for(i=0;i<N;i++)
{
scanf("%s",ttt);
sz[i]=strlen(ttt);
xx[0].clear();
for(j=0;j<sz[i];j++) xx[0].push_back(cha[ttt[j]]);
xx[1].clear();
for(j=0;j<sz[i];j++) xx[1].push_back(cha[ttt[sz[i]-j-1]]);
all[0].push_back(xx[0]);
all[1].push_back(xx[1]);
build(0,i,0);
build(1,i,0);
}
BFS(0,0);
BFS(1,0);
for(i=0;i<N;i++)
{
con=sz[i];
xx[0]=all[0][i];
where[i].first=Find(0,0).first;
xx[0]=all[1][i];
where[i].second=Find(1,0).first;
add(where[i].first,where[i].second,0);
}
while(M--)
{
scanf("%s",ttt);
xx[0].clear();
con=strlen(ttt);
for(j=0;j<con;j++) xx[0].push_back(cha[ttt[j]]);
a=Find(0,0);
scanf("%s",ttt);
xx[0].clear();
con=strlen(ttt);
for(j=0;j<con;j++) xx[0].push_back(cha[ttt[con-j-1]]);
b=Find(1,0);
if(a.first==-1||b.first==-1) printf("0\n");
else
{
ans=0;
for(i=0;i<N;i++)
{
if(a.first<=where[i].first&&where[i].first<=a.second)
{
if(b.first<=where[i].second&&where[i].second<=b.second) ans++;
}
}
printf("%d\n",ans);
}
}
return 0;
}
