import java.util.*;
public class Main{
    static int N=1010;
    static String[]strs=new String[N];
    static int [][]f=new int [N][N];
    //此题没有将字符串转换成 char[] 没有再 前面加'x' 索引有所变化
    static int getDis(String a,String b){
        int n=a.length();
        int m=b.length();
        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]=Math.min(f[i][j-1]+1,f[i-1][j]+1);
                //注意此处索引是从0开始的  所以 要取 i-1；j-1；而f的索引从1开始；
                f[i][j]=Math.min(f[i][j],f[i-1][j-1]+(a.charAt(i-1)==b.charAt(j-1)?0:1));
            }
        }
        return f[n][m];
    }
    public static void main(String[]args){
        Scanner sc=new Scanner (System.in);
        String[]ps1=sc.nextLine().split(" ");
        int n=Integer.parseInt(ps1[0]);
        int m=Integer.parseInt(ps1[1]);
        for(int i=0;i<n;i++){
            strs[i]=sc.nextLine();
        }

        while(m-->0){
            String[]ps2=sc.nextLine().split(" ");
            int limit=Integer.parseInt(ps2[1]);
            int res=0;
            for(int i=0;i<n;i++){
                if(getDis(ps2[0],strs[i])<=limit)res++;
            }
            System.out.println(res);
        }
    }
}