import java.io.*;
import java.util.*;

class Main {

    //存放所有原始串
    static List<char[]> list = new ArrayList<>();
    //状态表示数组
    static int[][] f = new int[1010][1010];
    //初始化边界
    static {
        for (int i = 1; i <= 1009; i++) {
            f[i][0] = i;
            f[0][i] = i;
        }
    }

    static int find(char[] p, int limt) {
        int cnt = 0;
        for (int k = 0; k < list.size(); k++) {
            char[] s = list.get(k);
            for (int i = 1; i <= s.length; i++)
                for (int j = 1; j <= p.length; j++) {
                    f[i][j] = Math.min(f[i-1][j],f[i][j-1]) + 1;
                    if (s[i-1] == p[j-1]) f[i][j] = Math.min(f[i][j],f[i-1][j-1]);
                    else f[i][j] = Math.min(f[i][j],f[i-1][j-1]+1);
                }
            if (f[s.length][p.length] <= limt) cnt++;
        }
        return cnt;
    }

    public static void main(String[] args) throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader in = new BufferedReader(isr);
        OutputStreamWriter osw = new OutputStreamWriter(System.out);
        BufferedWriter out = new BufferedWriter(osw);


        String[] strs = in.readLine().split(" ");
        int n = Integer.parseInt(strs[0]);
        int m = Integer.parseInt(strs[1]);
        for (int i = 1; i <= n; i++) {
            char[] s = in.readLine().toCharArray();
            list.add(s);
        }

        for (int i = 1; i <= m; i++){
            strs = in.readLine().split(" ");
            char[] p = strs[0].toCharArray();
            int limt = Integer.parseInt(strs[1]);
            out.write(find(p, limt)+"\n");
        }


        in.close();
        isr.close();
        out.flush();
        out.close();
        osw.close();
    }
}