#include<bits/stdc++.h> using namespace std; const int N=1e5+7; map<string, int> tt, ht; int n, q, mt, mh; string s[N], a[N], b[N]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>q; for(int i=1; i<=n; i++) cin>>s[i]; for(int i=1; i<=q; i++) { cin>>a[i]>>b[i]; int v=a[i].size(), u=b[i].size(); mt=max(mt, v); mh=max(mh, u); } for(int i=1; i<=n; i++) { int v=s[i].size(); string re=""; for(int j=0; j<min(v, mt); j++) { re+=s[i][j]; tt[re]++; } } for(int i=1; i<=n; i++) { int v=s[i].size(); string re=""; for(int j=v-1; j>=v-min(v,mh); j--) { re=s[i][j]+re; ht[re]++; } } for(int i=1; i<=q; i++) { cout<<min(tt[a[i]], ht[b[i]])<<"\n"; } }