#include <bits/stdc++.h>
#define ll long long
#define s second
#define pb push_back
#define f first
#define left (h<<1),l,((l+r)>>1)
#define right ((h<<1)|1),((l+r)>>1) + 1,r
#define int ll
using namespace std;
const int N = 5005,mod = 1000000007;
int len[N],h[N][N],p[N];
signed main (){
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
int n,m;
cin>>n>>m;
p[0] = 1;
for (int i = 1; i <= 5000; i++)
p[i] = (p[i - 1]*31)%mod;
for (int i = 1; i <= n; i++){
string s;
cin>>s;
len[i] = s.size();
for (int j = 0; j < len[i]; j++){
if(j) h[i][j] = (h[i][j - 1] + (p[j]*(s[j] - 'A' + 1))%mod)%mod;
else h[i][j] = (s[j] - 'A' + 1);
}
}
while(m--){
string a,b;
cin>>a>>b;
int cnt=0,A = a.size(),B = b.size(),ha = 0,hb = 0;
for (int i = 0; i < A; i++) ha = (ha + (p[i]*(a[i] - 'A' + 1)))%mod;
for (int i = 0; i < B; i++) hb = (hb + (p[i]*(b[i] - 'A' + 1)))%mod;
for (int i = 1; i <= n; i++){
int Ha = h[i][A - 1];
if (Ha != ha) continue;
int Hb = ((h[i][len[i] - 1] - h[i][len[i] - B - 1])%mod + mod)%mod;
if (Hb == (hb*p[len[i] - B])%mod) cnt++;
}
cout<<cnt<<"\n";
}
}
