"""
基本思想：
1. 将n个字符串存到数组s_arr中
2. 依次遍历m个询问字符串和操作次数上限，遍历s_arr数组中的字符串，分别计算每个询问字符串和第j个操作字符串的操作次数(思路参考"最短编辑距离")，将操作次数与操作次数上限进行比较，小于操作上限次数则count加1

输入样例：
3 2
abc
acd
bcd
ab 1
acbd 2
输出样例：
1
3
"""

def editDistance(s1, s2):
    lenOfS1 = len(s1)-1    # !!!出错：因为s1和s2用空白符填充了第一位，所以s1和s2的长度应该减1
    lenOfS2 = len(s2)-1

    # 2. 初始化dp数组
    dp = [[0 for j in range(lenOfS2+1)] for i in range(lenOfS1+1)]
    for i in range(lenOfS1+1):
        dp[i][0] = i
    for i in range(lenOfS2+1):
        dp[0][i] = i

    # 3. 状态计算
    for i in range(1, lenOfS1+1):
        for j in range(1, lenOfS2+1):
#             print(i,j)
            dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1)    # !!!出错：忘记加1了
            if s1[i]==s2[j]:
                dp[i][j] = min(dp[i][j], dp[i-1][j-1])
            else:
                dp[i][j] = min(dp[i][j], dp[i-1][j-1]+1)
    return dp[lenOfS1][lenOfS2]

# 1. 输入示例
n, m = map(int, input().split())

s_arr = []
for i in range(n):
    s_arr.append(" " + input().strip())

for i in range(m):
    in_li = input().split()
    s = " " + in_li[0]
    limit = int(in_li[1])
    count = 0
    for string in s_arr:
        if editDistance(string, s)<=limit:
            count += 1
    print(count)