def print_hi():
    line1 = input()
    line1 = line1.split(" ")
    num_of_burners = int(line1[1])
    word = input()
    res = []

    for i in range(num_of_burners):
        result = 0
        _ = input()
        search_string = input()


        old_word = word
        word = word.replace(search_string, "", 1)
        if word != old_word:
            result += 1

        print(result)


"""
        for j in range(num_of_books + 1 - substring_len):
            if word[j] == search_string[counter]:
                counter += 1

                if counter == substring_len - 1:
                    result += 1                      
                    word = word.replace(search_string, "", 1)
"""



if __name__ == '__main__':
    print_hi()