#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int maxn=5e3+5;
const int base=31;
const ll MOD=1e9+7;
int n,m;
string s[maxn];
string p,q;
vector<ll> Hs[maxn];
ll Pow[100005];
ll get(int i,int j,int k)
{
return (Hs[k][j]-Hs[k][i-1]*Pow[j-i+1]+MOD*MOD)%MOD;
}
int main()
{
Pow[0]=1;
for(int i=1;i<=1e5;i++) Pow[i]=(Pow[i-1]*base)%MOD;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s[i];
int len=s[i].size();
s[i]=" "+s[i];
Hs[i].push_back(0);
for(int j=1;j<=len;j++){
Hs[i].push_back((Hs[i][j-1]*base+s[i][j]-'A'+1)%MOD);
}
}
for(int i=1;i<=m;i++){
cin>>p>>q;
ll hp=0,hq=0;
for(int j=0;j<p.size();j++) hp=(hp*base+p[j]-'A'+1)%MOD;
for(int j=0;j<q.size();j++) hq=(hq*base+q[j]-'A'+1)%MOD;
int ans=0;
for(int j=1;j<=n;j++){
ll pre=get(1,p.size(),j);
ll suf=get(s[j].size()-q.size(),s[j].size()-1,j);
if(pre==hp&&suf==hq) ans++;
}
cout<<ans<<'\n';
}
}
