#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
using namespace std;
const int N=2e6+6;
int n,m;
int trie[3],timer[3];
int G[2*N],ANS[N],T[2*N][5][3],in[N][3],out[N][3];
string u,q;
pair < int , int > d[2*N];
vector < pair < bool , int > > v[2*N][3];
inline int C(char c) {
if (c=='A') return 0;
if (c=='C') return 1;
if (c=='G') return 2;
return 3;
}
pair < int , int > idx;
void Upd(int id,int x,bool ty) {
if (u.size()==x) {
v[id][ty].pb(idx);
return ;
}
int t=C(u[x]);
if (!T[id][t][ty]) T[id][t][ty]=++trie[ty];
Upd(T[id][t][ty],x+1,ty);
}
void Dfs(int x,int ty) {
++timer[ty];
for (int i=0; i<v[x][ty].size(); i++) {
int type=v[x][ty][i].F,idx=v[x][ty][i].S;
if (!type) {
if (!ty)
d[idx].F=timer[ty];
else
d[idx].S=timer[ty];
}
else in[idx][ty]=timer[ty];
}
for (int i=0; i<4; i++)
if (T[x][i][ty])
Dfs(T[x][i][ty],ty);
for (int i=0; i<v[x][ty].size(); i++) {
int type=v[x][ty][i].F,idx=v[x][ty][i].S;
if (type) out[idx][ty]=timer[ty];
}
}
void Up(int x) {
while (x<=2*N-5) {
G[x]++;
x+=(x & -x);
}
}
int Get(int x) {
int res=0;
while (x>0) {
res+=G[x];
x-=(x & -x);
}
return res;
}
main () {
ios_base::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
cin>>n>>m;
for (int i=1; i<=n; i++) {
cin>>u;
idx={0,i};
Upd(0,0,0);
reverse(u.begin(),u.end());
Upd(0,0,1);
}
for (int i=1; i<=m; i++) {
cin>>u>>q;
idx={1,i};
Upd(0,0,0);
reverse(q.begin(),q.end()); u=q;
Upd(0,0,1);
}
Dfs(0,0);
Dfs(0,1);
vector < pair < int , pair < int , int > > > Q;
for (int i=1; i<=m; i++) {
Q.pb({in[i][0]-1,{-1,i}});
Q.pb({out[i][0],{1,i}});
}
sort(d+1,d+n+1);
sort(Q.begin(),Q.end());
int j=0;
for (int i=0; i<Q.size(); i++) {
int qy=Q[i].F,dl=Q[i].S.F,id=Q[i].S.S;
while (j+1<=n && d[j+1].F<=qy) {
++j;
Up(d[j].S);
}
ANS[id]+=dl*(Get(out[id][1])-Get(in[id][1]-1));
}
for (int i=1; i<=m; i++)
cout<<ANS[i]<<"\n";
}
