#include <bits/stdc++.h>
//#define int long long
#define mp make_pair
#define pb push_back
#define ld long double
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define piii pair<pii,pii>
#define precise cout<<fixed<<setprecision(10)
#define st first
#define nd second
#define ins insert
#define vi vector<int>
#define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int MAXN=1e5+5;
const int MAXT=2e6+5;
const int inf=(int)1e9+9;
string S[MAXN];
string P[MAXN];
string Q[MAXN];
int syn[MAXT][4];
int mini[MAXT];
int maxi[MAXT];
vi ids[MAXT];
int f(char x){
if (x=='A')return 0;
if (x=='G')return 1;
if (x=='C')return 2;
return 3;
}
int cnt=0;
pii przedzial[MAXN];
void update(int u,int x){
mini[u]=min(mini[u],x);
maxi[u]=max(maxi[u],x);
}
void wstaw1(string s,int id){
int u=0;
update(u,id);
for (auto it:s){
int to=f(it);
if (!syn[u][to])syn[u][to]=++cnt;
u=syn[u][to];
update(u,id);
}
}
void wstaw2(string s,int id){
int u=0;
ids[u].pb(id);
for (auto it:s){
int to=f(it);
if (!syn[u][to])syn[u][to]=++cnt;
u=syn[u][to];
ids[u].pb(id);
}
}
pii search1(string s){
int u=0;
for (auto it:s){
int to=f(it);
if (!syn[u][to])return mp(inf,-inf);
u=syn[u][to];
}
return mp(mini[u],maxi[u]);
}
vi search2(string s){
int u=0;
for (auto it:s){
int to=f(it);
if (!syn[u][to])return {};
u=syn[u][to];
}
return ids[u];
}
int func(vi &v,int l,int r){
if (l>r)return 0;
if (v.empty())return 0;
if (r<v[0] || l>v.back())return 0;
auto itl=lower_bound(v.begin(),v.end(),l)-v.begin();
auto itr=(--upper_bound(v.begin(),v.end(),r))-v.begin();
return (int)itr-(int)itl+1;
}
int32_t main(){
BOOST;
fill(mini,mini+MAXT,inf);
fill(maxi,maxi+MAXT,-inf);
int n,m;
cin>>n>>m;
for (int i=1;i<=n;i++)cin>>S[i];
sort(S+1,S+n+1);
for (int i=1;i<=n;i++)wstaw1(S[i],i);
for (int i=1;i<=m;i++){
cin>>P[i]>>Q[i];
przedzial[i]=search1(P[i]);
}
for (int i=0;i<MAXT;i++)for (int j=0;j<4;j++)syn[i][j]=0;
cnt=0;
for (int i=1;i<=n;i++){
reverse(S[i].begin(),S[i].end());
wstaw2(S[i],i);
}
for (int i=1;i<=m;i++){
reverse(Q[i].begin(),Q[i].end());
vi v=search2(Q[i]);
cout<<func(v,przedzial[i].st,przedzial[i].nd)<<"\n";
}
return 0;
}
