/**
 * Author             : Dipu Kumar Mohanto (Dip)
 *                      CSE, BRUR.
 *
 * Problem            : 1427 - Substring Frequency (II)
 * Algorithm          : Aho - Corasik
 * Complexity         : O(q*(len+|p|)
 * Category           : String, string matching
 *
 * Source             : LIGHT Online Judge
 *
 * Verdict            : Accepted
 *
 * Date               :
 * E-mail             : dipukumarmohanto1@gmail.com
**/

#include <bits/stdc++.h>

using namespace std;

const int mx = 510;

struct node {
    int cnt;
    bool vis;

    node* next[27];

    vector <node *> out;

    node() {
        cnt = 0;
        vis = false;

        for (int i=0; i<27; i++)
            next[i] = NULL;

        out.clear();
    }

    ~node() {
        for (int i=1; i<27; i++) {
            if (next[i] != NULL && next[i] != this)
            {
                delete next[i];
            }
        }
    }
}*root;


void buildTrie(char dictionary[][mx], int n)
{
    // dictionary[][] = all query word
    // n              = total query word

    root = new node();

    // usual trie tree
    for (int i=0; i<n; i++)
    {
        node* a = root;

        for (int j=0; dictionary[i][j]; j++)
        {
            int id = dictionary[i][j] - 'a' + 1;

            if (a->next[id] == NULL)
                a->next[id] = new node();

            a = a->next[id];
        }
    }

    // Pushing adjacent node to root into queue
    queue <node *> PQ;

    for (int i=0; i<27; i++)
    {
        if (root->next[i] == NULL)
        {
            root->next[i] = root;
        }

        else
        {
            PQ.push(root->next[i]);

            root->next[i]->next[0] = root;  // ->next[0] = back pointer
        }
    }

    //Building Aho - Corasik tree
    while (!PQ.empty())
    {
        node* u = PQ.front();   // parent node
        PQ.pop();

        for (int i=1; i<27; i++)
        {
            if (u->next[i])
            {
                node* v = u->next[i];   // child node
                node* w = u->next[0];   // back pointer of parent node

                while (!w->next[i])     // untill the char (i - 'a' + 1) child is not found
                    w = w->next[0];

                v->next[0] = w = w->next[i];  // back pointer of v will be found child above
                w->out.push_back(v);    // out will be used in dfs
                                        // here w is the new found match node
                PQ.push(v);
            }
        }
    }
}



// Third step processing the text
void aho_corasik(node* p, char *word)
{
    for (int i=0; word[i]; i++)
    {
        int id = word[i] - 'a' + 1;

        while (!p->next[id])
            p = p->next[0];

        p = p->next[id];
        p->cnt++;
    }
}

// DFS for counting
int dfs(node* p)
{
    if (p->vis)
        return p->cnt;

    for (int i=0; i<(int)p->out.size(); i++)
        p->cnt += dfs(p->out[i]);

    p->vis = true;

    return p->cnt;
}

char str[1000000 + 100];
char dictionary[mx][mx];



int main()
{
    //freopen("in.txt", "r", stdin);

    int tc;
    scanf("%d", &tc);

    for (int tcase=1; tcase<=tc; tcase++)
    {
        int Q; // query
        scanf("%d", &Q);

        scanf("%s", str);

        for (int i=0; i<Q; i++)
            scanf("%s", dictionary[i]);

        buildTrie(dictionary, Q);
        aho_corasik(root, str);

        printf("Case %d:\n", tcase);

        for (int i=0; i<Q; i++)
        {
            node* p = root;

            for (int j=0; dictionary[i][j]; j++)
            {
                int id = dictionary[i][j] - 'a' + 1;
                p = p->next[id];
            }
            printf("%d\n", dfs(p));
        }
        delete root;
    }
    return 0;
}