// Template generated by Clank
#include<bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define all(x) x.begin(), x.end()
#define BOOST cin.tie(NULL); ios_base::sync_with_stdio(false);
// #define int ll
typedef long long ll;
pair<int,int> pzero = {-1,-1};
struct Node{
int next[30] = {0};
int nw = 0;
int l = 1e9, r = 0;
vector<int> ids;
};
struct Trie{
int root = 1;
int prectr = 1;
vector<Node> t;
Trie(){
t.resize(2);
}
void add_string(string &s, int id){
int idx = root;
// cout << t[idx].next[0] << " lol\n";
for(auto c : s){
if(!t[idx].next[c - 'A']){
t[idx].next[c - 'A'] = (int)t.size();
t.emplace_back();
}
idx = t[idx].next[c - 'A'];
}
t[idx].ids.push_back(id);
t[idx].nw++;
}
int dfs(int idx, vector<pair<int,int>> &labels){
// static int prectr = 1;
t[idx].l = prectr;
for(int i : t[idx].ids){
labels[i].st = prectr++;
t[idx].r = labels[i].st;
}
for(int i = 0; i < 30; i++){
if(t[idx].next[i] != 0){
t[idx].r = max(t[idx].r, dfs(t[idx].next[i], labels));
}
}
return t[idx].r;
}
pair<int,int> get_lim(string &s){
int idx = root;
// cout << s << "\n";
for(int i = 0; i < (int)s.size(); i++){
if(t[idx].next[s[i] - 'A'] == 0) return pzero;
idx = t[idx].next[s[i] - 'A'];
// cout << idx << "\n";
}
return {t[idx].l - 1, t[idx].r};
}
};
struct SegTree{
int n;
int shift = 1;
vector<int> t;
SegTree(int inn) : n(inn){
while(shift < n) shift <<= 1;
t.resize(2 * shift);
}
void update(int idx, int val){
for(idx += shift; idx >= 1; idx >>= 1){
t[idx] += val;
}
}
int query(int l, int r){
int sum = 0;
for(l += shift, r += shift; l < r; l >>= 1, r >>= 1){
if(l&1) sum += t[l++];
if(r&1) sum += t[--r];
}
return sum;
}
};
void compute_rect(int n, vector<pair<int,int>> &labels, vector<pair<pair<int,int>, pair<int,int>>> &queries, map<pair<int,int>, int> &rect){
vector<pair<pair<int,int>, int>> points;
for(int i = 0; i < n; i++){
points.push_back({labels[i], -1});
}
for(auto i : queries){
if(i.st == pzero || i.nd == pzero) continue;
points.push_back({{i.st.st, i.nd.st}, 0});
points.push_back({{i.st.st, i.nd.nd}, 0});
points.push_back({{i.st.nd, i.nd.st}, 0});
points.push_back({{i.st.nd, i.nd.nd}, 0});
}
SegTree tree(n + 5);
sort(all(points));
for(auto p : points){
if(p.nd == 0){
rect[p.st] = tree.query(0, p.st.nd + 1);
} else {
tree.update(p.st.nd, abs(p.nd));
}
}
}
int32_t main(){
BOOST;
int n, m; cin >> n >> m;
string notes;
Trie pre;
Trie suf;
for(int i = 0; i < n; i++){
cin >> notes;
pre.add_string(notes,i);
reverse(all(notes));
suf.add_string(notes, i);
}
vector<pair<int,int>> labels(n);
suf.dfs(1, labels);
for(int i = 0; i < n; i++) swap(labels[i].st, labels[i].nd);
pre.dfs(1, labels);
vector<pair<pair<int,int>, pair<int,int>>> queries;
string sp, ss;
for(int i = 0; i < m; i++){
cin >> sp >> ss;
reverse(all(ss));
queries.push_back({pre.get_lim(sp), suf.get_lim(ss)});
}
// for(int i = 0; i < n; i++){
// cout << labels[i].st << " - " << labels[i].nd << "\n";
// }
// cout << "\n";
// for(auto i : queries){
// cout << i.st.st << " " << i.st.nd << " " << i.nd.st << " " << i.nd.nd << "\n";
// }
// cout << labels << "\n";
// cout << queries << "\n";
map<pair<int,int>, int> rectangles;
compute_rect(n, labels, queries, rectangles);
// for(auto i : rectangles){
// cout << i.st.st << " " << i.st.nd << " - " << i.nd << "\n";
// }
int sum = 0;
for(auto i : queries){
sum = 0;
if(i.st == pzero || i.nd == pzero){
cout << 0 << "\n";
continue;
}
sum += rectangles[{i.st.st, i.nd.st}];
sum -= rectangles[{i.st.st, i.nd.nd}];
sum -= rectangles[{i.st.nd, i.nd.st}];
sum += rectangles[{i.st.nd, i.nd.nd}];
cout << sum << "\n";
}
return 0;
}
