#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

char mg[1510][12];
char qu[1010][12];
int th[1010];
int n, m;
int mgl[1510];
int qul[1010];
int ans[1010];

int levenDistance(char a[], char b[]){
    int d[12][12];
    int i, j;
    int la = strlen(a);
    int lb = strlen(b);
    memset(d, 0, sizeof(d));
    for(i = 0; i <= la; i ++)
        d[i][0] = i;
    for(j = 0; j <= lb; j ++)
        d[0][j] = j;
    for(j = 1; j <= lb; j ++)
        for(i = 1; i <= la; i ++){
            if(a[i] == b[j]){
                d[i][j] = d[i-1][j-1];
            }
            else{
                d[i][j] = min(d[i-1][j]+1, min(d[i][j-1]+1, d[i-1][j-1]+1));
            }
        }
    //printf("%s %s\n", a, b);
    //printf("%d\n", d[la][lb]);
    return d[la][lb];
}

int main(){
    int t;
    int i, j;
    int cnt = 0;
    scanf("%d", &t);
    while(t --){
        cnt ++;
        char ss[12];
        memset(ans, 0, sizeof(ans));
        scanf("%d %d", &n, &m);
        for(i = 0; i < n; i ++){
            scanf("%s", ss);
            mg[i][0] = 's';
            mg[i][1] = '\0';
            strcat(mg[i], ss);
            mgl[i] = strlen(mg[i]);
        }
        for(i = 0; i < m; i ++){
            scanf("%s", ss);
            qu[i][0] = 's';
            qu[i][1] = '\0';
            strcat(qu[i], ss);
            qul[i] = strlen(qu[i]);
            scanf("%d", &th[i]);
        }
        for(i = 0; i < m; i ++){
            for(j = 0; j < n; j ++){
                if(abs(qul[i] - mgl[j]) <= th[i]){
                    if(levenDistance(mg[j], qu[i]) <= th[i])
                        ans[i] ++;
                }
            }
        }
        printf("Case #%d:\n", cnt);
        for(i = 0; i < m; i ++)
            printf("%d\n", ans[i]);
    }
    return 0;
}