def main():
    l1 = input()
    _, burners_num = l1.split(" ")
    burners_num = int(burners_num)
    word = input()

    word = word.strip()

    res = ""
    p = 0
    while p < burners_num:
        p+=1
        input()
        word_to_find = input()

        i =0
        k=0
        w_l = len(word_to_find)
        word_len = len(word)
        if w_l > word_len:
            res+="0\n"
            continue

        res_i = 0
        while k < word_len:
            if word_len+1-i < w_l:
                break

            if k-i >= w_l-1:
                res_i +=1
                word = word[:i]+word[k+1:]
                word_len = len(word)

                k = i
                continue
            flag = False
            if word_to_find[k-i] != word[k]:
                i=k
                k-=1

            k+=1

        res+=f"{res_i}\n"

    res = res.strip("\n")
    print(res)

main()