#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct trie1 {
vector<unordered_map<char, int>> a;
vector<int> l, r;
int n = 0;
int oo = 1e9;
unordered_map<char, int> temp;
void start() {
a.push_back(temp);
l.push_back(oo);
r.push_back(0);
}
void add(string s, int id) {
int pos = 0;
for (int i = 0; i < s.length(); i++) {
if (a[pos][s[i]] == 0) {
a[pos][s[i]] = ++n;
a.push_back(temp);
l.push_back(id);
r.push_back(id);
pos = n;
} else {
pos = a[pos][s[i]];
}
r[pos] = id;
}
}
pair<int, int> query(string s) {
int pos = 0;
for (auto i : s) {
if (a[pos].find(i) == a[pos].end()) return {-1, -1};
pos = a[pos][i];
}
return {l[pos], r[pos]};
}
};
struct trie2 {
vector<unordered_map<char, int>> a;
vector<vector<int>> b;
int n = 0;
unordered_map<char, int> temp;
void start() {
a.push_back(temp);
b.push_back({});
}
void add(string s, int id) {
int pos = 0;
for (int i = 0; i < s.length(); i++) {
if (a[pos][s[i]] == 0) {
a[pos][s[i]] = ++n;
a.push_back(temp);
b.push_back({});
pos = n;
} else {
pos = a[pos][s[i]];
}
b[pos].push_back(id);
}
}
int query(string s) {
int pos = 0;
for (auto i : s) {
if (a[pos].find(i) == a[pos].end()) return -1;
pos = a[pos][i];
}
return pos;
}
};
const int MAX = 1e5 + 2;
int n, q;
string a[MAX];
void solve() {
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
trie1 chemwy;
trie2 cheemwy;
chemwy.start();
cheemwy.start();
for (int i = 1; i <= n; i++) {
chemwy.add(a[i], i);
reverse(a[i].begin(), a[i].end());
cheemwy.add(a[i], i);
}
for (int i = 1; i <= cheemwy.n; i++) sort(cheemwy.b[i].begin(), cheemwy.b[i].end());
for (int i = 1; i <= q; i++) {
string s, t;
cin >> s >> t;
reverse(t.begin(), t.end());
auto [l, r] = chemwy.query(s);
if (l == -1) {
cout << 0 << "\n";
continue;
}
int temp = cheemwy.query(t);
if (temp == -1) {
cout << 0 << "\n";
continue;
}
int x = upper_bound(cheemwy.b[temp].begin(), cheemwy.b[temp].end(), r) - cheemwy.b[temp].begin() - 1;
int y = lower_bound(cheemwy.b[temp].begin(), cheemwy.b[temp].end(), l) - cheemwy.b[temp].begin();
cout << x - y + 1 << "\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
