import java.util.*;

class Main {

    public static int editDist(String str, String target) {
        int n = str.length(), m = target.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= m; i++)
            dp[0][i] = i;
        for (int i = 0; i <= n; i++)
            dp[i][0] = i;

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                char ct = target.charAt(i);
                char cs = str.charAt(j);
                dp[j + 1][i + 1] = dp[j][i + 1] + 1; // Delete
                dp[j + 1][i + 1] = Math.min(dp[j + 1][i + 1], dp[j + 1][i] + 1); // insert
                dp[j + 1][i + 1] = Math.min(dp[j + 1][i + 1], dp[j][i] + 1); // replace
                if (ct == cs)
                    dp[j + 1][i + 1] = Math.min(dp[j + 1][i + 1], dp[j][i]); // equals
            }
        return dp[n][m];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt(); // n: stirng m: query times
        String[] strs = new String[n];
        for (int i = 0; i < n; i++)
            strs[i] = sc.next();

        String[] query = new String[m];
        int[] maxOps = new int[m];
        for (int i = 0; i < m; i++) {
            query[i] = sc.next();
            maxOps[i] = sc.nextInt();
        }

        for (int i = 0; i < m; i++) {
            int cnt = 0;
            for (int j = 0; j < n; j++) {
                int val  = editDist(strs[j], query[i]);
                if (editDist(strs[j], query[i]) <= maxOps[i])
                    cnt++;
            }
            System.out.println(cnt);
        }
    }
}