#include<iostream>
#include<cstring>
using namespace std;
int n,m,f[15][15],i,j;
char c[1005][15];
int ed_dist(char a[],char b[])
{
    int la=strlen(a+1),lb=strlen(b+1);
    for(i=0;i<=lb;i++)f[0][i]=i;
    for(i=0;i<=la;i++)f[i][0]=i;
    for(i=1;i<=la;i++)
        for(j=1;j<=lb;j++)f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1),[i][j]=min(f[i][j],f[i-1][j-1]+(a[i]!=b[j]));
    return f[la][lb];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)scanf("%s",c[i]+1);
    while(m--){
        char s[15];
        int limit,ans=0;
        scanf("%s%d",s+1,&limit);
        for(i=0;i<n;i++)if(ed_dist(c[i],s)<=limit)ans++;
        printf("%d\n",ans);
    }
    return 0;
}