#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
//Note to self: Check for overflow
const int N=6'000'006;
struct pers_segtree
{
int val[N],L[N],R[N];
int idx=0;
int root[200005];
//root se podrazumeva da je kec (1)
void add(int p, int q, int l, int r, int s, int x)
{
val[p]=val[q]+x;
if (l==r) return;
int mid=(l+r)/2;
if (s<=mid) L[p]=++idx,R[p]=R[q],add(L[p],L[q],l,mid,s,x);
else L[p]=L[q],R[p]=++idx,add(R[p],R[q],mid+1,r,s,x);
}
int sum(int p, int q, int l, int r, int ll, int rr)
{
if (ll>r || rr<l) return 0;
if (ll<=l && rr>=r) return val[p]-val[q];
int mid=(l+r)/2;
return sum(L[p],L[q],l,mid,ll,rr)+sum(R[p],R[q],mid+1,r,ll,rr);
}
} ST;
struct nicetrie
{
int idx=1;
int node[2000006][4];
vector<int> inds[2000006];
int tin[2000006],tout[2000006];
int perm[2000006];
//root se podrazumeva da je kec (1)
void add(string &s, int ind)
{
int p=1;
for (auto c : s)
{
int gde;
if (c=='A') gde=0;
else if (c=='C') gde=1;
else if (c=='G') gde=2;
else gde=3;
if (!node[p][gde]) node[p][gde]=++idx;
p=node[p][gde];
}
inds[p].pb(ind);
}
int VREME=1;
void dfs(int p)
{
tin[p]=VREME;
for (auto it : inds[p]) perm[VREME++]=it;
ff(i,0,4) if (node[p][i]) dfs(node[p][i]);
tout[p]=VREME;
}
pii le_find(string &s)
{
int p=1;
for (auto c : s)
{
int gde;
if (c=='A') gde=0;
else if (c=='C') gde=1;
else if (c=='G') gde=2;
else gde=3;
p=node[p][gde];
if (!p) return {-1,-1};
}
return {tin[p],tout[p]-1};
}
} pref, suf;
int gdeusuf[200005];
int sami[200005];
int main()
{
FAST;
int n,q; cin>>n>>q;
fff(i,1,n)
{
string s; cin>>s;
pref.add(s,i);
reverse(all(s));
suf.add(s,i);
}
pref.dfs(1);
suf.dfs(1);
fff(i,1,n) gdeusuf[suf.perm[i]]=i;
fff(i,1,n) sami[i]=gdeusuf[pref.perm[i]];
ST.root[0]=++ST.idx;
fff(i,1,n)
{
ST.root[i]=++ST.idx;
ST.add(ST.root[i],ST.root[i-1],1,n,sami[i],1);
}
while (q--)
{
string a,b; cin>>a>>b; reverse(all(b));
auto [l1,r1]=pref.le_find(a);
auto [l2,r2]=suf.le_find(b);
//cout<<"["<<l1<<","<<r1<<"] x ["<<l2<<","<<r2<<"]: ";
if (l1>r1 || l2>r2 || l1==-1 || l2==-1 || r1==-1 || r2==-1) cout<<0<<"\n";
else cout<<ST.sum(ST.root[r1],ST.root[l1-1],1,n,l2,r2)<<"\n";
}
}
//Note to self: Check for overflow
