1 #include <cstdio>
 2 #include <cstring>
 3 #define min(x,y) (x < y ? x : y)
 4 #define unequal(x,y) (x == y ? 0 : 1)
 5 #define MAX 12
 6 #define INF (1<<30)
 7 using namespace std;
 8 
 9 char s[1502][MAX];
10 char c[MAX];
11 int dp[MAX][MAX];
12 
13 int deal(int a){
14     int l1,l2;
15     l1=strlen(s[a]+1);
16     l2=strlen(c+1);
17     for(int i=0;i<=l1;i++) dp[i][0]=i;
18     for(int j=0;j<=l2;j++) dp[0][j]=j;
19     for(int i=1;i<=l1;i++){
20         for(int j=1;j<=l2;j++){
21             dp[i][j]=INF;
22         }
23     }

24     for(int i=1;i<=l1;i++){
25         for(int j=1;j<=l2;j++){
26             dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);
27             dp[i][j]=min(dp[i][j],dp[i-1][j-1]+unequal(s[a][i],c[j]));
28         }
29     }
30     return dp[l1][l2];
31 }
32 
33 int main()
34 {
35     int t,n,m,e,th,count;
36     //freopen("data.txt","r",stdin);
37     scanf("%d",&t);
38     for(int z=1;z<=t;z++){
39         printf("Case #%d:\n",z);
40         scanf("%d %d",&n,&m);
41         for(int i=0;i<n;i++){
42             scanf("%s",s[i]+1);
43         }
44         while(m--){
45             scanf("%s %d",c+1,&th);
46             count=0;
47             for(int i=0;i<n;i++){
48                 e=deal(i);
49                 //printf("%d ",e);
50                 if(e<=th) count++;
51             }
52             //printf("\n");
53             printf("%d\n",count);
54         }
55     }
56     return 0;
57 }