HA55

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    int counter;

    TrieNode() : counter(0) {}
};

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }

    void insert(const string& word) {
        TrieNode* node = root;
        node->counter++; // увеличиваем счетчик в корне
        for (char ch : word) {
            if (!node->children.count(ch)) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
            node->counter++;
        }
    }

    int query(const string& word) {
        TrieNode* node = root;
        int depth = 0;
        for (char ch : word) {
            if (!node->children.count(ch)) {
                break;
            }
            node = node->children[ch];
            ++depth;
        }
        return node->counter + depth;
    }

private:
    TrieNode* root;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    Trie trie;
    for (int i = 0; i < n; ++i) {
        string word;
        cin >> word;
        trie.insert(word);
    }

    int q;
    cin >> q;
    while (q--) {
        string query;
        cin >> query;
        cout << trie.query(query) << '\n';
    }

    return 0;
}