#include <string>
#include <iostream>
#include <fstream>
#include <list>
#include <algorithm>
#include <set>
#include <vector>

#include <boost/unordered_set.hpp>
#include <boost/spirit/include/classic.hpp>
#include <boost/shared_array.hpp>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/foreach.hpp>

#define foreach BOOST_FOREACH

namespace detail
{
    struct cstring_equal
    {
        bool operator () (const char* lhs, const char* rhs) const
        {
            return strcmp(lhs, rhs) == 0;
        }
    };

    struct cstring_less
    {
        bool operator () (const char* lhs, const char* rhs) const
        {
            return strcmp(lhs, rhs) == -1;
        }
    };

    // string pool
    // only grow, never shrinks
    class string_pool
    {
        struct buffer_t
        {
            boost::shared_array<char> buffer;
            char* pos;
            size_t size;

            buffer_t(size_t s)
                : size(s)
            {
                buffer.reset(new char[size]);
                pos = buffer.get();
            }

            char* begin()
            {
                return pos;
            }

            char* end()
            {
                return buffer.get() + size;
            }

            size_t capacity()
            {
                return end() - pos;
            }

            buffer_t& operator += (size_t s)
            {
                pos += s;
                assert(pos <= end());
                return *this;
            }
        };
        std::list<buffer_t> buffers_;
        static const size_t BUFFER_SIZE = 0x4000;
    public:

        const char* append(const char* str)
        {
            size_t len = strlen(str) + 1;
            if (buffers_.empty() || len > buffers_.back().capacity())
            {
                //calc new size
                size_t buffer_size = len < BUFFER_SIZE ? BUFFER_SIZE : len;
                buffers_.push_back( buffer_t(buffer_size) );
            }
            char* pos = buffers_.back().begin();
            memcpy((void*)pos, (const void*)str, len);
            buffers_.back() += len;
            return pos;
        }
    };
}


class Query
{
    std::vector<std::string> levels_;
public:
    typedef std::vector<std::string>::iterator iterator;
    typedef std::vector<std::string>::const_iterator const_iterator;
    Query()
    {
    }
    
    void add_level(char const* b, char const* e)
    {
        levels_.push_back(std::string(b, e));
    }

    void add_level(char c)
    {
        levels_.push_back(std::string(1, c));
    }

    iterator begin()
    {
        return levels_.begin();
    }

    iterator end()
    {
        return levels_.end();
    }

    const_iterator begin() const
    {
        return levels_.begin();
    }

    const_iterator end() const
    {
        return levels_.end();
    }
};

class LangTable
{
    struct Node
    {
        char alpha;
        Node* children[26];

        Node(char alpha) 
            : alpha(alpha)
            , children()
        {
        }

        bool operator < (Node const& n)
        {
            return (alpha < n.alpha);
        }

        Node* operator [] (char c)
        {
            assert(('a' <= c) && (c <= 'z'));
            return children[c - 'a'];
        }

        void append(char const* word)
        {
            if(*word)
            {
                char hd = *word;
                Node* p = children[hd - 'a'];
                if (p == 0)
                {
                    p = new Node(hd);
                    children[hd - 'a'] = p;
                }
                p->append(word + 1);
            }
        }

        int query_count(Query::const_iterator begin, Query::const_iterator end)
        {
            if(begin == end)
            {
                return 1;
            }

            int counter = 0;
            std::string line = *begin;
            foreach(char a, line)
            {
                Node* p = children[a - 'a'];
                if (p)
                {
                    counter += p->query_count(begin + 1, end);
                }
            }
            return counter;
        }
    };

    typedef detail::string_pool StringPool;

    StringPool pool_;
    Node root_;
    int wordlen_;
public:

    LangTable(int wordlength)
        : wordlen_(wordlength)
        , root_('*')
    {
    }

    // build
    void add(const char* word)
    {
        root_.append(word);
    }

    // lookup
    int count(Query const& query)
    {
        return root_.query_count(query.begin(), query.end());
    }
};



struct QueryAction
{
    Query& query;

    QueryAction(Query& q) : query(q) {}

    void operator () (char c) const
    {
        query.add_level(c);
    }

    void operator () (char const* b, char const* e) const
    {
        query.add_level(b, e);
    }
};

void parse_line(char const* line, int wordlen, Query& query)
{
    using namespace boost::spirit::classic;

    QueryAction query_a(query);
    rule<phrase_scanner_t> variant_p = confix_p( "("
                                               , (*anychar_p)[query_a]
                                               , ")"
                                               );

    rule<phrase_scanner_t> word = repeat_p(wordlen)
                                  [
                                      (   variant_p
                                      |   anychar_p[query_a]
                                      )
                                  ];

    if (parse(line, word, space_p).full == false) 
        throw std::runtime_error("format error");
}


int main(int argc, char* argv[])
{
    if (argc < 3) 
    {
        std::cout << "not enough parameters" << std::endl;
        return -1;
    }

    std::fstream file; 
    std::fstream output(argv[2], std::ios::out);
    file.open(argv[1], std::ios::in);

    if (file.fail())
    {
        throw std::runtime_error("can't open file");
    }

    {
        int L = 0, D = 0, N = 0;

        file >> L >> D >> N;
        file.get();

        LangTable alang(L);

        char buffer[0x10000];

        // read D words
        for(int i = 0; i < D; ++i)
        {
            file.peek();
            if (file.eof())
                break;
            // read
            file.getline(buffer, 0x10000);
            alang.add(buffer);
        }

        // read N test cases
        for(int i = 0; i < N; ++i)
        {
            file.peek();
            if (file.eof())
                break;

            // read
            file.getline(buffer, 0x10000);

            Query q;
            parse_line(buffer, L, q);

            //eval
            int count = alang.count(q);

            // output
            output << "Case #" << (i + 1) << ": " << count << std::endl;
        }
    }
    file.close();
    output.close();
	return 0;
}