#include<bits/stdc++.h>
#define ll long long
#define nl "\n"
#define all(v) v.begin(),v.end()
#define baraa ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
bool check(string s, string suffix) {
ll n = s.size(), m = suffix.size(), i = n - 1, j = m - 1;
while (i >= 0 && j >= 0) {
if (s[i] != suffix[j])return 0;
i--, j--;
}
return (j == -1);
}
struct node1 {
map<char, ll> mp;
ll ends = 0;
ll &operator[](char c) {
return mp[c];
}
};
struct miniTrie {
vector<node1> tree;
vector<string> strings;
ll newNode() {
tree.emplace_back();
return tree.size() - 1;
}
miniTrie() {
tree.clear();
strings.clear();
newNode();
}
void insert(string s) {
strings.push_back(s);
reverse(all(s));
ll u = 0;
for (auto c: s) {
if (!tree[u][c])
tree[u][c] = newNode();
u = tree[u][c];
tree[u].ends++;
}
}
ll get(string suffix) {
reverse(all(suffix));
ll u = 0;
for (auto c: suffix) {
if (!tree[u][c])return 0;
u = tree[u][c];
}
return tree[u].ends;
}
ll size() {
return strings.size();
}
};
struct node {
map<char, ll> mp;
miniTrie a;
vector<pair<string, ll> > qu;
ll ends = 0;
ll &operator[](char c) {
return mp[c];
}
void insS(string s) {
a.insert(s);
}
void insQ(string s, ll idx) {
qu.push_back({s, idx});
}
};
struct Trie {
vector<node> tree;
ll newNode() {
tree.emplace_back();
return tree.size() - 1;
}
Trie() {
tree.clear();
newNode();
}
void insert(string s) {
ll u = 0;
for (auto c: s) {
if (!tree[u][c])
tree[u][c] = newNode();
u = tree[u][c];
}
tree[u].insS(s);
tree[u].ends++;
}
ll get(string suffix) {
ll u = 0;
for (auto c: suffix) {
if (!tree[u][c])return 0;
u = tree[u][c];
}
return tree[u].ends;
}
void query(string prefix, string suffix, ll idx) {
ll u = 0;
for (auto c: prefix) {
if (!tree[u][c])return;
u = tree[u][c];
}
tree[u].insQ(suffix, idx);
}
void dfs(ll u, vector<ll> &res) {
// cout << u << nl;
for (auto [ch, v]: tree[u].mp) {
if (!v)continue;
// cout << ch << nl;
dfs(v, res);
if (tree[u].a.size() < tree[v].a.size())swap(tree[u].a, tree[v].a);
for (auto s: tree[v].a.strings)tree[u].a.insert(s);
}
// cout << u << nl;
// for (auto s: tree[u].a.strings)
// cout << s << nl;
for (auto &[suffix, idx]: tree[u].qu) {
res[idx] += tree[u].a.get(suffix);
// for (auto s: tree[u].a.strings)
// res[idx] += check(s, suffix), cout << s << ' ' << suffix << ' ' << check(s, suffix) << nl;
}
}
};
int main() {
baraa
ll n, q;
cin >> n >> q;
Trie trie;
for (ll i = 0; i < n; i++) {
string s;
cin >> s;
trie.insert(s);
}
vector<ll> res(q);
for (ll i = 0; i < q; i++) {
string prefix, suffix;
cin >> prefix >> suffix;
trie.query(prefix, suffix, i);
}
trie.dfs(0, res);
for (ll i: res)cout << i << nl;
return 0;
}
