#include <iostream>
#include <string>
using namespace std;
const int max_child = 676;
string pre, suf;
int x, y;
struct Trie {
struct node {
node *child[max_child];
int cnt;
node () {
fill_n(child, max_child, nullptr);
cnt = 0;
}
};
node *root;
Trie () {
root = new node();
}
void add_string(const string &s) {
node *cur = root;
int n = s.length();
for (int i = 0; i < n; ++i) {
int p = (s[i] - 'A') * 26 + (s[n - i - 1] - 'A');
if (cur->child[p] == nullptr) cur->child[p] = new node();
cur = cur->child[p];
++cur->cnt;
}
}
void solve(int &ans, const int i, node *cur) {
if (i == max(x, y)) {
ans += cur->cnt;
return;
}
if (i < min(x, y)) {
int p = (pre[i] - 'A') * 26 + (suf[y - i - 1] - 'A');
if (cur->child[p] == nullptr) return;
solve(ans, i + 1, cur->child[p]);
} else {
if (i < x) {
for (int j = 0, p = (pre[i] - 'A') * 26; j < 26; ++j, ++p) {
if (cur->child[p] != nullptr) {
solve(ans, i + 1, cur->child[p]);
}
}
} else {
for (int j = 0, p = suf[y - i - 1] - 'A'; j < 26; ++j, p += 26) {
if (cur->child[p] != nullptr) solve(ans, i + 1, cur->child[p]);
}
}
}
}
} T;
int n, q;
string s;
int main() {
cin.tie(nullptr);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);
cin >> n >> q;
while (n--) {
cin >> s;
T.add_string(s);
}
while (q--) {
cin >> pre >> suf;
x = pre.length();
y = suf.length();
int ans = 0;
T.solve(ans, 0, T.root);
cout << ans << "\n";
}
return 0;
}
