#include<bits/stdc++.h>
using namespace std;
using ll=long long;
//#pragma GCC optimize("03,unroll-loops")
//#pragma GCC target("avx2")
//#pragma GCC target("sse4")
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
//#define randi uniform_int_distribution<long long>
#define damoon(v) v.resize(unique(all(v))-v.begin())
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//randi dist(0,10000000000000000);
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,bool> pib;
typedef pair<long long,bool> plb;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
typedef pair<string,string> pss;
typedef vector<int> veci;
typedef vector<long long> vecl;
typedef vector<bool> vecb;
typedef vector<pii> vecp;
typedef set<int> seti;
typedef set<long long> setl;
typedef set<pii> setp;
typedef map<int,int> mapii;
typedef map<long long,long long> mapll;
typedef map<int,bool> mapib;
typedef map<long long,bool> maplb;
const int inf=1e9,mod=1e9+7,neginf=-1e9;
const double PI=acos(-1);
struct Trie
{
vector<array<int,4>> nxt;
Trie()
{
nxt.pub({-1,-1,-1,-1});
}
int ind(char c)
{
if(c=='A')
return 0;
if(c=='C')
return 1;
if(c=='G')
return 2;
return 3;
}
int Add()
{
nxt.pub({-1,-1,-1,-1});
return (int)nxt.size()-1;
}
int insert(const string &s)
{
int v=0;
for(char c:s)
{
int i=ind(c);
if(nxt[v][i]==-1)
nxt[v][i]=Add();
v=nxt[v][i];
}
return v;
}
int check(const string &s)
{
int v=0;
for(char c:s)
{
int i=ind(c);
if(nxt[v][i]==-1)
return -1;
v=nxt[v][i];
}
return v;
}
int size() const
{
return (int)nxt.size();
}
};
void bfs(const Trie &T,veci &tin,veci &tout)
{
int n=T.size();
tin.assign(n,0);
tout.assign(n,0);
int tim=0;
vecp st;
st.reserve(n);
st.emplace_back(0,0);
while(st.size())
{
auto &pr=st.back();
int u=pr.F;
int &ch=pr.S;
if(ch==0)
tin[u]=++tim;
if(ch<4)
{
int v=T.nxt[u][ch];
ch++;
if(v!=-1)
{
st.emplace_back(v,0);
}
}
else
{
tout[u]=tim;
st.pob();
}
}
}
struct Fenwick
{
int n;
veci f;
Fenwick(int m)
{
n=m;
f.assign(n+1,0);
}
void update(int i,int v)
{
for(;i<=n;i+=i&-i)
f[i]+=v;
}
int sum(int i)
{
int s=0;
for(;i>0;i-=i&-i)
s+=f[i];
return s;
}
int get(int l,int r)
{
if(r<l)
return 0;
return sum(r)-sum(l-1);
}
};
struct Point
{
int x,y;
};
struct Event
{
int x,ly,ry,id,c;
};
bool cmpp(Point &a,Point &b)
{
return a.x<b.x;
}
bool cmpe(Event &a,Event &b)
{
if(a.x!=b.x)
return a.x<b.x;
return a.c<b.c;
}
void solve()
{
int n,m;
cin>>n>>m;
vector<string> ss(n);
for(int i=0;i<n;i++)
cin>>ss[i];
vector<pss> Qs(m);
for(int i=0;i<m;i++)
cin>>Qs[i].F>>Qs[i].S;
Trie Prf;
veci prt(n);
for(int i=0;i<n;i++)
prt[i]=Prf.insert(ss[i]);
Trie Suf;
veci sft(n);
for(int i=0;i<n;i++)
{
string s=ss[i];
reverse(all(s));
sft[i]=Suf.insert(s);
}
veci tinp,toutp;
bfs(Prf,tinp,toutp);
veci tins,touts;
bfs(Suf,tins,touts);
vector<Point> pts;
pts.reserve(n);
for(int i=0;i<n;i++)
pts.pub({tinp[prt[i]],tins[sft[i]]});
sort(all(pts),cmpp);
vector<Event> evs;
evs.reserve(2*m);
vecl ans(m,0);
for(int i=0;i<m;i++)
{
const string &p=Qs[i].F;
const string &q=Qs[i].S;
int np=Prf.check(p);
if(np==-1)
{
ans[i]=0;
continue;
}
string rq=q;
reverse(all(rq));
int nq=Suf.check(rq);
if(nq==-1)
{
ans[i]=0;
continue;
}
int lx=tinp[np],rx=toutp[np];
int ly=tins[nq],ry=touts[nq];
evs.pub({rx-0,ly,ry,i,+1});
evs.pub({lx-1,ly,ry,i,-1});
}
sort(all(evs),cmpe);
int may=(int)Suf.size()+10;
Fenwick Fen(may);
int pind=0;
for(auto &ev:evs)
{
while(pind<(int)pts.size() and pts[pind].x<=ev.x)
{
Fen.update(pts[pind].y,1);
pind++;
}
ll cnt=Fen.get(ev.ly,ev.ry);
ans[ev.id]+=ev.c*cnt;
}
for(int i=0;i<m;i++)
cout<<ans[i]<<"\n";
}
int main()
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(false);
//ifstream fin("in.txt");
//ofstream fout("out.txt");
int t=1;
//cin>>t;
while(t--)
{
solve();
}
}
