#include <iostream>
#include <string.h>
using namespace std;
int n,m;
const int N=1005;
int f[N][N];
char str[N][N];
bool pan(char a[],char s[],int k)
{
    int len1=strlen(a+1),len2=strlen(s+1);
    for(int i=1; i<=len1; i++)
        for(int j=1; j<=len2; j++)
            f[i][j]=1e9;
    for(int i=1; i<=len1; i++)
        f[i][0]=i;
    for(int i=1; i<=len2; i++)
        f[0][i]=i;

    for(int i=1; i<=len1; i++)
        for(int j=1; j<=len2; j++)
        {
            f[i][j]=min(f[i-1][j],f[i][j-1])+1;
            if(a[i]==s[j])
                f[i][j]=min(f[i][j],f[i-1][j-1]);
            else
                f[i][j]=min(f[i][j],f[i-1][j-1]+1);
        }
    //cout<<a<<endl;
    // cout<<f[strlen(a)][strlen(s)]<<endl;;
    return f[len1][len2]<=k;
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        cin>>str[i]+1;
    }
    while(m--)
    {
        char s[N];
        int k;
        cin>>s+1>>k;
        int res=0;
        for(int i=1; i<=n; i++)
        {
            if(pan(str[i],s,k))
                res++;
        }
        cout<<res<<endl;
    }
    //cout << "Hello world!" << endl;
    return 0;
}