#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e6+10,mod=1e9+7,base=26;
string s[N],p[N],q[N];
ll pw[N],inv[N];
char cur[]={'A','A','C','G','U'};
vector<ll> pre[N];
ll gethash(int i,int l,int r) // 1-base and inc inc
{
ll k1=(pre[i][r]-pre[i][l-1]+mod)%mod;
// pre[r] has power (r-1) we need its power to be r-l
// pre[l] has power l-1 we need its power to be l-1
// so mul by inverse of
return (k1*inv[l-1])%mod;
}
int powmod(int a,int b)
{
int ans=1;
while(b)
{
if(b&1)
ans=(1ll*ans*a)%mod;
a=(1ll*a*a)%mod;
b>>=1;
}
return ans;
}
int main()
{
ios::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
pw[0]=1;
for(int i=1;i<N;i++)
{
pw[i]=(1ll*pw[i-1]*base)%mod;
}
inv[N-1]=powmod(pw[N-1],mod-2);
for(int i=N-2;i>=0;i--)
{
inv[i]=(1ll*inv[i+1]*base)%mod;
}
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>s[i];
int sz=s[i].size();
pre[i].resize(sz+1);
for(int j=0;j<sz;j++)
{
for(int p=1;p<=4;p++)
{
if(s[i][j]==cur[p])
{
pre[i][j+1]=(1ll*pre[i][j]+1ll*p*pw[j])%mod;
}
}
}
}
vector<int> pos,qos;
for(int i=0;i<m;i++)
{
cin>>p[i]>>q[i];
pos.push_back(p[i].size());
qos.push_back(q[i].size());
}
sort(begin(pos),end(pos));
pos.resize(unique(begin(pos),end(pos))-begin(pos));
sort(begin(qos),end(qos));
qos.resize(unique(begin(qos),end(qos))-begin(qos));
unordered_map<ll,int> cnt;
// ll st=4e18;
// cout<<st<<endl;
for(int i=0;i<n;i++)
{
// check prefix only for length in pos, and suffix for length in q
int sz=s[i].size();
for(auto&l:pos)
{
if(l>sz)break;
int h1=gethash(i,1,l);
// till here iteration can be maximum sum(len(s[i]))<=2e6
for(auto&l1:qos) // sqrt(2e6)
{
if(l1>sz)break;
int h2=gethash(i,sz-l1+1,sz);
// cout<<"For "<<i<<' '<<l<<' '<<l1<<' '<<h1<<' '<<h2<<endl;
cnt[(1ll*h1*mod)+h2]++;
}
}
}
for(int i=0;i<m;i++)
{
int hash=0;
for(int j=0;j<p[i].size();j++)
{
for(int k=1;k<=4;k++)
{
if(p[i][j]==cur[k])
{
hash=(1ll*hash+1ll*k*pw[j])%mod;
}
}
}
int hash1=0;
for(int j=0;j<q[i].size();j++)
{
for(int k=1;k<=4;k++)
{
if(q[i][j]==cur[k])
{
hash1=(1ll*hash1+1ll*k*pw[j])%mod;
}
}
}
// cout<<hash<<' '<<hash1<<endl;
cout<<cnt[(1ll*hash*mod)+hash1]<<'\n';
}
// A C G U
// 0 1 2 3
}
