#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace BIT{
int t = 0;
const int OFFSET = 10;
vector<vector<pair<int, int>>> a;
void init(int n){
a.resize(n + OFFSET*2, vector<pair<int, int>> (1, pair<int, int> (-1, 0)));
}
void update(int pos, int val){
for (pos += OFFSET; pos < a.size(); pos += pos & (-pos))
a[pos].emplace_back(t, a[pos].back().second + val);
t++;
}
int query(int pos, int t){
int v = 0;
for (pos += OFFSET; pos; pos -= pos & (-pos)){
vector<pair<int, int>> &x = a[pos];
int p = lower_bound(x.begin(), x.end(), pair<int, int> (t, INT_MAX)) - x.begin() - 1;
v += x[p].second;
}
return v;
}
}
vector<pair<string, int>> a, b;
signed main(){
cin.tie(0)->sync_with_stdio(0);
int n, m; cin >> n >> m;
{
for (int i=0; i<n; i++){
string ss; cin >> ss;
a.emplace_back(ss, i);
reverse(ss.begin(), ss.end());
b.emplace_back(ss, i);
}
stable_sort(a.begin(), a.end());
stable_sort(b.begin(), b.end());
vector<int> p(n), s(n);
for (int i=0; i<n; i++){
p[a[i].second] = i;
s[b[i].second] = i;
}
BIT::init(n);
for (pair<string, int> &x: a){
BIT::update(s[x.second], 1);
}
}
while (m--){
string p; cin >> p;
int startp = lower_bound(a.begin(), a.end(), pair<string, int> (p, 0)) - a.begin();
int endp = lower_bound(a.begin(), a.end(), pair<string, int> (p + '[', 0)) - a.begin() - 1;
string q; cin >> q;
reverse(q.begin(), q.end());
int startq = lower_bound(b.begin(), b.end(), pair<string, int> (q, 0)) - b.begin();
int endq = lower_bound(b.begin(), b.end(), pair<string, int> (q + '[', 0)) - b.begin() - 1;
if (startp > endp || startq > endq){
cout << "0\n";
}
else{
int s = BIT::query(endq, endp) - BIT::query(startq-1, endp);
int t = BIT::query(endq, startp-1) - BIT::query(startq-1, startp-1);
cout << s - t << "\n";
}
}
}
