#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define sz(x) (int) x.size()
#define pb push_back
const int mxN = 1e5+5;
const int mC = 2e6+5;
int n;
int v[mC];
vector<int> idxs[mC];
vector<int> adj[mC];
int cnt = 0;
int dfs(int node, int l, int r, int idx, string &s){
if (idx == 0){
return lower_bound(idxs[node].begin(), idxs[node].end(),r) - lower_bound(idxs[node].begin(),idxs[node].end(),l);
}
for (int i : adj[node]){
if (v[i] == s[idx-1]-'A') return dfs(i,l,r,idx-1,s);
}
return 0;
}
void add(int node, int cidx, int idx, string &s){
idxs[node].pb(cidx);
if (idx == 0) return;
for (int i : adj[node]){
if (v[i] == s[idx-1]-'A') return add(i,cidx,idx-1,s);
}
v[cnt] = s[idx-1] - 'A';
adj[node].pb(cnt);
cnt++;
return add(cnt-1,cidx,idx-1,s);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int m;
cin >> n >> m;
vector<string> all(n);
for (int i = 0; i < n; i++) cin >> all[i];
sort(all.begin(),all.end());
string temp;
v[0] = 1;
cnt++;
for (int i = 0; i < n; i++){
temp = all[i]+'B';
add(0,i,sz(temp)-1,temp);
}
int l,r;
string a,b;
for (int i = 0; i < m; i++){
cin >> a >> b;
l = lower_bound(all.begin(),all.end(), a) - all.begin();
r = lower_bound(all.begin(),all.end(), a+'Z') - all.begin();
temp = b + 'B';
cout << dfs(0,l,r,sz(temp)-1,temp) << '\n';
}
return 0;
}
