#include <bits/stdc++.h>
#define int long long
#define ll long long
#define el endl
#define pb push_back
#define all(x) begin(x), end(x)
using namespace std;
const int modd = 1e9 + 7;
void MO() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
struct Node {
unordered_map<char, int> nxt;
int isEnd = 0, sz = 0;
int &operator[](char x) {
return nxt[x];
}
};
struct Trie {
vector<Node> tr;
int M = 'Z'+4;
vector<ll> l, r; // start & end for each id
vector<vector<ll>> b;
int newNode() {
tr.emplace_back();
l.emplace_back();
r.emplace_back();
b.emplace_back();
return tr.size() - 1;
}
Trie() {
tr.clear();
newNode();
}
int id = 0;
void insert(string &s) {
id++;
int u = 0;
for (char c: s) {
if (!tr[u][c]) {
tr[u][c] = newNode();
l[tr[u][c]] = id;
r[tr[u][c]] = id;
}
tr[u].sz++;
u = tr[u][c];
r[u] = id;
b[u].push_back(id);
}
tr[u].sz++;
tr[u].isEnd++;
r[u] = id;
b[u].push_back(id);
}
pair<ll, ll> startWith(string &s) {
int u = 0;
for (char c: s) {
if (!tr[u][c]) return {-1, -1};
u = tr[u][c];
}
return {l[u], r[u]};
}
ll startWithSuf(string &s) {
int u = 0;
for (char c: s) {
if (!tr[u][c]) return -1;
u = tr[u][c];
}
return u;
}
};
void solve() {
ll n, q;
cin >> n >> q;
vector<string> data;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
data.pb(s);
}
sort(all(data));
Trie trprefix;
Trie trsuffix;
// string ee = "hel",ee1 ="hen",e = "he";
// trprefix.insert(ee);
// trprefix.insert(ee1);
// cout << trprefix.startWith(e).second << el;
for (int i = 0; i < n; i++) {
trprefix.insert(data[i]);
string rev = data[i];
reverse(all(rev));
trsuffix.insert(rev);
}
// Sort all b vectors for binary search
for (int i = 0; i < trsuffix.tr.size(); i++) {
sort(all(trsuffix.b[i]));
}
for (ll i = 0; i < q; i++) {
string s, t;
cin >> s >> t;
reverse(all(t));
auto [l, r] = trprefix.startWith(s);
if (l == -1) {
cout << 0 << el;
continue;
}
int temp = trsuffix.startWithSuf(t);
if (temp == -1) {
cout << 0 << el;
continue;
}
// Find count of elements in trsuffix.b[temp] that are in range [l, r]
auto &vec = trsuffix.b[temp];
int left_idx = lower_bound(all(vec), l) - vec.begin();
int right_idx = upper_bound(all(vec), r) - vec.begin();
cout << right_idx - left_idx << el;
}
}
signed main() {
MO();
int t = 1;
while (t--) {
solve();
}
}
