#include <bits/stdc++.h>
// #include <bits/extc++.h>
// #include <ext/pb_ds/hash_policy.hpp>
// #include <ext/pb_ds/>
using namespace std;
// using namespace __gnu_pbds;
#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];
vector<int> qos[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;
ll lm=1e8;
for(int i=0;i<m;i++)
{
cin>>p[i]>>q[i];
// if((1ll*n*m)<=lm)
// {
// 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;
// }
// }
// }
// int ans=0;
// for(int j=0;j<n;j++)
// {
// if(p[i].size()>s[j].size() or q[i].size()>s[j].size())continue;
// if(gethash(j,1,p[i].size())==hash and gethash(j,s[j].size()-q[i].size()+1,s[j].size())==hash1)
// {
// ans++;
// }
// }
// cout<<ans<<endl;
// continue;
// }
pos.push_back(p[i].size());
qos[p[i].size()].push_back(q[i].size());
}
if(pos.size()==0)return 0;
sort(begin(pos),end(pos));
pos.resize(unique(begin(pos),end(pos))-begin(pos));
for(int l=1;l<N;l++)
{
if(qos[l].size()==0)continue;
sort(begin(qos[l]),end(qos[l]));
qos[l].resize(unique(begin(qos[l]),end(qos[l]))-begin(qos[l]));
}
// gp_hash_table<ll,int> cnt;
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);
for(auto&l1:qos[l])
{
if(l1>sz)break;
int h2=gethash(i,sz-l1+1,sz);
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
}
