#include <bits/stdc++.h>

using namespace std;
const int N = 15;
const int M = 1010;

int n, m;
int f[N][N];
char str[M][N];

int edit_distance(char a[], char b[]) {
    int la = strlen(a + 1), lb = strlen(b + 1);
    for (int i = 0; i <= lb; i++) f[0][i] = i;
    for (int i = 0; i <= la; i++) f[i][0] = i;
    for (int i = 1; i <= la; i++)
        for (int j = 1; j <= lb; j++) {
            // 增加和删除
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            // 修改
            if (a[i] == b[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);
        }
    return f[la][lb];
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> (str[i] + 1); // 二维数组，躲开第一列
    while (m--) {
        char s[N];
        int limit;
        cin >> (s + 1) >> limit;
        int res = 0;
        for (int i = 0; i < n; i++)
            if (edit_distance(str[i], s) <= limit) res++;
        cout << res << endl;
    }
    return 0;
}