#include <iostream>
#include <string>
#include <vector>
#include <math.h>
using namespace std;
constexpr int N = 1e5 + 5;
constexpr int L = 2e6 + 5;
constexpr int MAX_NODES = static_cast<int>(L + L * log2(N));
struct Node;
struct NodePtr {
int id;
NodePtr() { }
NodePtr(int id) : id(id) { }
operator int() const { return id; }
Node *operator->() const;
NodePtr operator[](const string &s) const;
};
struct Node {
int count;
NodePtr children[4];
};
Node trie[MAX_NODES];
int num_nodes = 0;
Node *NodePtr::operator->() const {
return &trie[id];
}
string chains[L];
vector<pair<string, int>> queries[L];
int answer[N];
void merge(NodePtr node1, NodePtr node2) {
node1->count += node2->count;
for (int i = 0; i < 4; i++) {
if (!node2->children[i]) continue;
if (!node1->children[i]) {
node1->children[i] = ++num_nodes;
}
merge(node1->children[i], node2->children[i]);
}
}
// {trie root, trie size}
pair<NodePtr, int> dfs(NodePtr node) {
int root = 0;
int size = 0;
for (NodePtr &child : node->children) {
if (!child) continue;
auto [child_root, child_size] = dfs(child);
if (child_size > size) {
size = child_size;
root = child_root;
}
child = child_root;
}
size -= num_nodes;
if (!root) {
root = ++num_nodes;
}
// cout << "hi, i'm " << node << " and my root is " << root << endl;
for (NodePtr child_root : node->children) {
if (!child_root || child_root == root) continue;
merge(root, child_root);
}
if (node->count) {
// cout << "heyy!! " << node << ": " << chains[node] << endl;
NodePtr node2 = root;
node2->count += node->count;
for (auto it = chains[node].rbegin(); it != chains[node].rend(); ++it) {
int dir = ((*it) >> 1) & 3;
if (!node2->children[dir]) {
node2->children[dir] = ++num_nodes;
}
node2 = node2->children[dir];
node2->count += node->count;
}
// cout << "node2 " << node2 << " received " << node->count << endl;
}
for (const auto &[q, i] : queries[node]) {
// cout << "answering " << chains[node] << ' ' << q << endl;
NodePtr node2 = root;
for (auto it = q.rbegin(); it != q.rend(); ++it) {
int dir = ((*it) >> 1) & 3;
if (!node2->children[dir]) {
goto next_query;
}
node2 = node2->children[dir];
}
answer[i] = node2->count;
next_query:
;
}
size += num_nodes;
return {root, size};
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// freopen("input.txt", "r", stdin);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
NodePtr node = 0;
for (char c : s) {
int dir = (c >> 1) & 3;
if (!node->children[dir])
node->children[dir] = ++num_nodes;
node = node->children[dir];
}
node->count++;
chains[node] = s;
}
for (int i = 1; i <= m; i++) {
string p, q;
cin >> p >> q;
NodePtr node = 0;
for (char c : p) {
int dir = (c >> 1) & 3;
if (!node->children[dir]) {
answer[i] = 0;
goto next;
}
node = node->children[dir];
}
chains[node] = p;
queries[node].emplace_back(q, i);
next:
;
}
dfs(NodePtr(0));
for (int i = 1; i <= m; i++) {
cout << answer[i] << '\n';
}
return 0;
}
