#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
const int N = 1e5 + 5, M = 2e6 + 5, INF = 1e9 + 7;
int n, m;
string s[N], q[N];
pii range[N];
int tid = 0, r1 = ++tid, r2, mx[M], mn[M], child[M][26];
vector<int> v[M];
int cnt(int id, pii range){
if(v[id].empty()) return 0;
return upper_bound(v[id].begin(), v[id].end(), range.second) - lower_bound(v[id].begin(), v[id].end(), range.first);
}
void add(int p, const string &s, int id){
for(char c : s){
int nxt = c - 'A';
if(!child[p][nxt]) child[p][nxt] = ++tid;
p = child[p][nxt];
mx[p] = max(mx[p], id);
mn[p] = min(mn[p], id);
}
}
void add1(int p, const string &s, int id){
for(char c : s){
int nxt = c - 'A';
if(!child[p][nxt]) child[p][nxt] = ++tid;
p = child[p][nxt];
v[p].push_back(id);
}
}
pii query(int p, const string &pre){
for(char c : pre){
int nxt = c - 'A';
if(!child[p][nxt]) return {-1, -1};
p = child[p][nxt];
}
return {mn[p], mx[p]};
}
int query1(int p, const string &pre, pii range){
for(char c : pre){
int nxt = c - 'A';
if(!child[p][nxt]) return 0;
p = child[p][nxt];
}
return cnt(p, range);
}
void solve(){
for(int i = 0; i < M; i++){
mx[i] = 0, mn[i] = INF;
}
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> s[i];
}
sort(s + 1, s + n + 1);
for(int i = 1; i <= n; i++){
add(r1, s[i], i);
reverse(s[i].begin(), s[i].end());
}
for(int i = 1; i <= m; i++){
string p;
cin >> p >> q[i];
reverse(q[i].begin(), q[i].end());
range[i] = query(r1, p);
}
tid = 0, r2 = ++tid;
memset(child, 0, sizeof child);
for(int i = 1; i <= n; i++){
add1(r2, s[i], i);
}
for(int i = 1; i <= m; i++){
int ans = 0;
if(range[i].first != -1) ans = query1(r2, q[i], range[i]);
cout << ans << '\n';
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
#define task "RNA"
if(fopen(task ".inp", "r")){
freopen(task ".inp", "r", stdin);
freopen(task ".out", "w", stdout);
}
solve();
}
