#include <bits/stdc++.h>
using namespace std;
#define int int64_t //be careful about this
#define endl "\n"
#define f(i, a, b) for (int i = int(a); i < int(b); ++i)
#define pr pair
#define ar array
#define fr first
#define sc second
#define vt vector
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(a) (a).begin(), (a).end()
#define allr(a) (a).rbegin(), (a).rend()
#define mem(a, b) memset(a, b, sizeof(a))
void setIO(string s = "") {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// remove this when size of input is not fixed.
cin.exceptions(cin.failbit);
cout.precision(15);
cout << fixed;
if (SZ(s)) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
}
template<const int ALPHABET>
struct prefix_tree {
struct trie_node {
int link[ALPHABET];
vector<int> who;
trie_node() {
memset(link, -1, sizeof(link));
}
};
vector<trie_node> trie;
prefix_tree() {
trie.emplace_back();
}
void create_node(int parent, int c) {
trie.emplace_back();
}
int get_or_create_node(int current, int c) {
if (trie[current].link[c] < 0) {
trie[current].link[c] = trie.size();
create_node(current, c);
}
return trie[current].link[c];
}
int insert_str(const string & str, const int & i) {
int current = 0;
for (char c: str) {
current = get_or_create_node(current, c - 'A');
trie[current].who.push_back(i);
}
return current;
}
ar<int,2> query(const string & str) {
int current = 0;
for (char c: str) {
if (trie[current].link[c - 'A'] < 0) return ar<int,2> {-1,-1};
current = trie[current].link[c - 'A'];
}
return ar<int,2> {trie[current].who.front(),trie[current].who.back()};
}
int query(const string & str, int L, int R) {
int current = 0;
for (char c: str) {
if (trie[current].link[c - 'A'] < 0) return int(0);
current = trie[current].link[c - 'A'];
}
return int(upper_bound(all(trie[current].who), R) - lower_bound(all(trie[current].who), L));
}
};
prefix_tree<26> trie, reverse_trie;
signed main() {
setIO();
int n, q;
cin >> n >> q;
vt<string> s(n);
for (auto & _s: s) cin >> _s;
sort(all(s));
f(i, 0, n) {
trie.insert_str(s[i], i);
reverse(all(s[i]));
reverse_trie.insert_str(s[i], i);
}
while (q--) {
string p, q;
cin >> p >> q;
auto [L, R] = trie.query(p);
reverse(all(q));
cout << reverse_trie.query(q, L, R) << endl;
}
}
