#include<bits/stdc++.h>
using namespace std;
struct node{
node *go[5];
int in,out;
node(){
for(int i=0;i<4;i++)go[i]=NULL;
in=out=0;
}
};
typedef node* pnode;
struct t{
int tme=0;
pnode rt=new node();
void add(string s){
if(!rt)rt=new node();
pnode x=rt;
for(auto a:s){
int id=a-'1';
if(!x->go[id])x->go[id]=new node();
x=x->go[id];
}
}
pair<int,int> g(string s){
pnode x=rt;
for(auto a:s){
int id=a-'1';
x=x->go[id];
}
return {x->in,x->out};
}
void dfs(pnode x){
x->in=++tme;
for(int i=0;i<4;i++){
if(x->go[i])dfs(x->go[i]);
}
x->out=tme;
}
}pre,suf;
vector<int>add[2000005];
vector<pair<pair<int,int>,int>>qr[2000005];
vector<pair<pair<int,int>,int>>ql[2000005];
int ans[2000005];
struct fenwick{
int info[2000015];
int n;
void build(int _n){
n=_n;
}
void upd(int id,int val){
if(id==0)return;
for(int i=id;i<=n;i+=i&-i)info[i]+=val;
}
int fans(int id){
int ans=0;
for(int i=id;i>0;i-=i&-i)ans+=info[i];
return ans;
}
}fw;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,m;cin>>n>>m;
vector<string>have;
//cerr<<"work\n";
for(int i=0;i<n;i++){
string s;cin>>s;
for(auto &x:s){
if(x=='A')x='1';
else if(x=='G')x='2';
else if(x=='C')x='3';
else x='4';
}
string rs=s;
reverse(rs.begin(),rs.end());
pre.add(s);
suf.add(rs);
have.push_back(s);
}
//cerr<<"work\n";
vector<pair<string,string>>v;
for(int i=0;i<m;i++){
string a,b;cin>>a>>b;
for(auto &x:a){
if(x=='A')x='1';
else if(x=='G')x='2';
else if(x=='C')x='3';
else x='4';
}
for(auto &x:b){
if(x=='A')x='1';
else if(x=='G')x='2';
else if(x=='C')x='3';
else x='4';
}
reverse(b.begin(),b.end());
pre.add(a);
suf.add(b);
v.push_back({a,b});
}
//cerr<<"work\n";
pre.dfs(pre.rt);
suf.dfs(suf.rt);
for(auto x:have){
auto tpre=pre.g(x);
reverse(x.begin(),x.end());
auto tsuf=suf.g(x);
add[tpre.first].push_back(tsuf.first);
//cerr<<tpre.first<<' '<<tsuf.first<<"\n";
}
for(int i=0;i<v.size();i++){
auto [p,s]=v[i];
auto tpre=pre.g(p);
auto tsuf=suf.g(s);
qr[tpre.second].push_back({{tsuf.first,tsuf.second},i});
ql[tpre.first-1].push_back({{tsuf.first,tsuf.second},i});
//cerr<<tpre.first<<" "<<tpre.second<<", "<<tsuf.first<<" "<<tsuf.second<<"\n";
}
fw.build(suf.tme+5);
for(int i=1;i<=pre.tme;i++){
for(auto x:add[i])fw.upd(x,1);
for(auto [range,id]:qr[i]){
auto [l,r]=range;
ans[id]+=fw.fans(r)-fw.fans(l-1);
}
for(auto [range,id]:ql[i]){
auto [l,r]=range;
ans[id]-=fw.fans(r)-fw.fans(l-1);
}
}
for(int i=0;i<m;i++)cout<<ans[i]<<"\n";
}
