#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x)  {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x)  {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x)  {return (x==0?-1:__builtin_ctzll(x));}

#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii; 
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
  int x=0,w=1; char c=getchar(); 
  while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
  while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
  return x*w;
}

const int N=1e5+5,M=2e6+5;
int n,m,p[N],len[N],l[N],r[N],mn[M],mx[M],ch1[M][4],ch2[M][4],tot1=1,tot2=1,cnt,ans[N],rt[M];
vi s[N],g[M],pre[N],suf[N],fin1[M],fin2[M];

int trans(char c) {
  if(c=='A') return 0;
  if(c=='U') return 1;
  if(c=='C') return 2;
  if(c=='G') return 3;
  assert(0);
}
vi read_string() {
  static char tmp[N]; scanf("%s",tmp+1);
  int k=strlen(tmp+1);
  vi res(k+1);
  rep(i,1,k) res[i]=trans(tmp[i]);
  return res;
}

namespace SegT {
  int ls[N<<5],rs[N<<5],s[N<<5],tot;
  int merge(int x,int y) {
    if(!x||!y) return x+y; s[x]+=s[y];
    ls[x]=merge(ls[x],ls[y]), ls[y]=merge(rs[x],rs[y]);
    return x;
  }
  void add(int &p,int l,int r,int x) { 
    if(!p) p=++tot; s[p]++;
    if(l==r) return; int mid=l+r>>1;
    if(x<=mid) add(ls[p],l,mid,x);
    else add(rs[p],mid+1,r,x);
  }
  int qry(int p,int l,int r,int x,int y) {
    if(!p||!x) return 0; int mid=l+r>>1;
    if(l==x&&r==y) return s[p];
    if(y<=mid) return qry(ls[p],l,mid,x,y);
    else if(x>mid) return qry(rs[p],mid+1,r,x,y);
    else return qry(ls[p],l,mid,x,mid)+qry(rs[p],mid+1,r,mid+1,y);
  }
}

void dfs1(int u) {
  mn[u]=cnt+1;
  for(int x:fin1[u]) p[x]=++cnt;
  mx[u]=cnt;
  rep(i,0,3) {
    int v=ch1[u][i]; if(!v) continue;
    dfs1(v); chmax(mx[u],mx[v]);
  }
}
void dfs2(int u) {
  rep(i,0,3) {
    int v=ch2[u][i]; if(!v) continue;
    dfs2(v); rt[u]=SegT::merge(rt[u],rt[v]);
  }
  for(int x:fin2[u]) SegT::add(rt[u],1,n,p[x]);
  for(int x:g[u]) ans[x]=SegT::qry(rt[u],1,n,l[x],r[x]);
}

signed main() {
  n=read(), m=read();
  rep(i,1,n) {
    s[i]=read_string(), len[i]=s[i].size()-1;
    int u=1;
    rep(j,1,len[i]) {
      if(!ch1[u][s[i][j]]) ch1[u][s[i][j]]=++tot1;
      u=ch1[u][s[i][j]];
    } fin1[u].eb(i);
    u=1;
    per(j,len[i],1) {
      if(!ch2[u][s[i][j]]) ch2[u][s[i][j]]=++tot2;
      u=ch2[u][s[i][j]];
    } fin2[u].eb(i);
  }
  dfs1(1);
  rep(i,1,m) {
    pre[i]=read_string(), suf[i]=read_string();
    int u=1,lenp=pre[i].size()-1,lens=suf[i].size()-1;
    rep(j,1,lenp) u=ch1[u][pre[i][j]];
    if(u) {
      l[i]=mn[u], r[i]=mx[u];
      u=1;
      per(j,lens,1) u=ch2[u][suf[i][j]];
      if(u) g[u].eb(i);
    }
  }
  dfs2(1);
  rep(i,1,m) printf("%d\n",ans[i]);
  return 0;
}