#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <map>
#include <set>
#include <regex>
#include <algorithm>

typedef unsigned long long int ulli;

ulli fact(int n, std::vector<ulli>& factCache)
{
    ulli lastFact = factCache[factCache.size() - 1];
    if (factCache.size() > n)
    {
        return factCache[n];
    }
    for (int i = factCache.size(); i <= n; ++i)
    {
        factCache.push_back(lastFact * i);
        lastFact *= i;
    }
    return factCache[n];
}

ulli binomial(int n, int k, std::vector<ulli>& factCache)
{
    return (fact(n, factCache)) / ((fact(k, factCache)) * (fact((n-k), factCache)));
}

struct binomialNum
{
    std::pair<int, int> duo;
    ulli val;

    bool operator <(const binomialNum& other) const
    {
        return val < other.val;
    }
};

int solve(std::vector<ulli>& cache)
{
    int input;
    std::cin >> input;

    if (input == 1)
        return 1;

    std::priority_queue<binomialNum, std::vector<binomialNum>, std::less<>> q;
    std::set<binomialNum> map;

    binomialNum first = {std::make_pair(2, 1), 2 };

    q.push(first  );
    map.insert(first);

    while (!q.empty())
    {
        binomialNum current = q.top();
        map.insert(current);

        ulli left = ((current.val) * current.duo.second)/(current.duo.first - current.duo.second + 1);
        ulli right = (current.val) * ((current.duo.first - current.duo.second)/(current.duo.second + 1));

        ulli aVal = left + current.val;
        ulli bVal = right + current.val;

        std::cout << current.duo.first << " nad " << current.duo.second << " = " << current.val << std::endl;

        binomialNum nextA = {std::make_pair(current.duo.first + 1, current.duo.second), aVal};
        binomialNum nextB = {std::make_pair(current.duo.first + 1, current.duo.second + 1), bVal};


        if (aVal == input || bVal == input)
            return nextA.duo.first + 1;

        bool containsA = map.find(nextA) != map.end();
        bool containsB = map.find(nextB) != map.end();

        q.pop();


        if (aVal == bVal)
        {
            if (aVal < input && !containsA) {
                q.push(nextA);
            }
        }
        else
        {
            if (aVal < input && !containsA) {
                q.push(nextA);
            }

            if (bVal < input && !containsB)
            {
                q.push(nextB);
                }

            }
    }
    return -1;
}

bool greater(std::string damaged, std::string undamaged)
{
    for(int i = 0; i < damaged.size(); i++)
    {
        if(!std::isdigit(damaged[i]))
            return false;
        if(damaged[i] < undamaged[i])
            return true;
    }
}

void regex()
{
    std::string *undamaged;
    std::pair<std::string, int> *damaged;
    int resultsIndex = 0;
    std::pair<int, int> *results;
    int undamagedSize;

    // Get undamaged numbers (TODO: Leading zeroes)
    std::cin >> undamagedSize;
    undamaged = new std::string[undamagedSize];
    for(int i = 0; i < undamagedSize; i++)
        std::cin >> undamaged[i];
    std::sort(undamaged, undamaged + undamagedSize);

    int damagedSize;
    std::cin >> damagedSize;

    // Check each damaged number
    damaged = new std::pair<std::string, int>[damagedSize];
    results = new std::pair<int, int>[damagedSize];
    std::string read_damaged;
    for(int i = 0; i < damagedSize; i++)
    {
        std::string str = "";
        std::cin >> read_damaged;
        for(char c : read_damaged)
        {
            if(c == '?')
                str += ".";
            else if(c == '*')
                str += ".*";
            else
                str += c;
        }
        damaged[i] = std::make_pair(str, i);
    }
    std::sort(damaged, damaged + damagedSize);

    int firstGood = 0;
    while(true)
    {
        if(damaged[0].first > undamaged[firstGood])
            firstGood++;
        else
            break;
    }
    for(int i = 0; i < damagedSize; i++)
    {
        int count = 0;

        std::regex reg(damaged[i].first);
        for(int j = firstGood; j < undamagedSize; j++)
        {
            if(std::regex_match(undamaged[j], reg))
                count++;
            else if(greater(damaged[i].first, undamaged[j]))
            {
                if(damaged[i].first.find('*') == std::string::npos)
                    firstGood = j;
                break;
            }
        }

        results[resultsIndex++] = std::make_pair(damaged[i].second, count);
    }

    sort(results, results + damagedSize);
    for(int i = 0; i < damagedSize; i++)
        std::cout << results[i].second << std::endl;

    delete[] damaged;
    delete[] undamaged;
}

int main() {

    regex();
    return 0;

    //std::regex reg("a.*");
    //std::string a  = "bbc";

    //std:: cout << (std::regex_match(a, reg) ? "true" : "false" ) << std::endl;

    std::vector<ulli> factCache;
    factCache.push_back(1);
    factCache.push_back(1);

    int input;

    std::cin >> input;

    for (int i = 0; i < input; ++i)
    {
        std::cout << solve(factCache) << std::endl;
    }


    return 0;
}