import java.io.*;
import java.util.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static int INF = 0x3f3f3f3f;
    public static int minEdit(String s1, String s2){
        int n1 = s1.length(), n2 = s2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];
        for(int i = 1; i <= n1; i++) dp[i][0] = i;
        for(int i = 1; i <= n2; i++) dp[0][i] = i;
        for(int i = 1; i <= n1; i++){
            for(int j = 1; j <= n2; j++){
                dp[i][j] = INF;
                dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
                dp[i][j] = Math.min(dp[i][j], 
                    dp[i - 1][j - 1] + (s1.charAt(i - 1) == s2.charAt(j - 1) ? 0: 1 ));
            }
        }
        return dp[n1][n2];
    }
    public static void main(String[] args) throws Exception{
        String[] ss = read.readLine().split(" ");
        int n = Integer.valueOf(ss[0]);
        int m = Integer.valueOf(ss[1]);
        String[] s = new String[n];
        for(int i = 0; i < n; i++){
            s[i] = read.readLine();
        }
        while(m -- > 0){
            int ans = 0;
            ss = read.readLine().split(" ");
            int limit = Integer.valueOf(ss[1]);
            for(int i = 0; i < n; i++){
                if(minEdit(s[i], ss[0]) <= limit) ans++;
            }
            System.out.println(ans);
        }

    }
}