#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;
const int N = 1e5 + 5, INF = 1e9 + 7;
int n, m;
string s[N];
struct node1{
node1 *child[26];
int mx, mn;
node1(){
for(int i = 0; i < 26; i++) child[i] = nullptr;
mx = 0, mn = INF;
}
};
node1 *r1 = new node1();
struct node2{
node2 *child[26];
vector<int> v;
node2(){
for(int i = 0; i < 26; i++) child[i] = nullptr;
v.clear();
}
int cnt(pii range){
if(v.empty()) return 0;
return upper_bound(v.begin(), v.end(), range.second) - lower_bound(v.begin(), v.end(), range.first);
}
};
node2 *r2 = new node2();
void add(node1 *p, const string &s, int id){
for(char c : s){
int nxt = c - 'A';
if(!p -> child[nxt]) p -> child[nxt] = new node1();
p = p -> child[nxt];
p -> mx = max(p -> mx, id);
p -> mn = min(p -> mn, id);
}
}
void add1(node2 *p, const string &s, int id){
for(char c : s){
int nxt = c - 'A';
if(!p -> child[nxt]) p -> child[nxt] = new node2();
p = p -> child[nxt];
p -> v.push_back(id);
}
}
pii query(node1 *p, const string &pre){
for(char c : pre){
int nxt = c - 'A';
if(!p -> child[nxt]) return {-1, -1};
p = p -> child[nxt];
}
return {p -> mn, p -> mx};
}
int query1(node2 *p, const string &pre, pii range){
for(char c : pre){
int nxt = c - 'A';
if(!p -> child[nxt]) return 0;
p = p -> child[nxt];
}
return p -> cnt(range);
}
void solve(){
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());
add1(r2, s[i], i);
}
for(int i = 1; i <= m; i++){
string p, q; cin >> p >> q;
reverse(q.begin(), q.end());
pii range = query(r1, p);
int ans = 0;
if(range.first != -1) ans = query1(r2, q, range);
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();
}
