#include <iostream>
#include <vector>
using namespace std;

const int N = 1010;
int n, m;
int f[15][15];

int getCnt(vector<string> &vs, string a, int lim)
{
    int ans = 0;
    for(string b : vs)
    {
        int n = a.size()-1, m = b.size()-1;
        for(int i=0; i<=n; i++)
            f[i][0] = i;
        for(int i=0; i<=m; i++)
            f[0][i] = i;

        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
            {
                f[i][j] = min(f[i-1][j], f[i][j-1]) + 1;
                f[i][j] = min(f[i][j], f[i-1][j-1]+(a[i]!=b[j]));
            }
        int cnt = f[n][m];
        if(cnt <= lim)
            ans++;
    }
    return ans;
}

int main()
{
    cin >> n >> m;
    vector<string> vs(n);
    for(int i=0; i<n; i++)
    {
        cin >> vs[i];
        vs[i] = " " + vs[i];
    }

    while(m--)
    {
        string t;
        int lim;
        cin >> t >> lim;
        t = " " + t;
        cout << getCnt(vs, t, lim) << endl;
    }
    return 0;
}