#include <algorithm>
#include <functional>
#include <iostream>
#include <string_view>

int main()
{
    std::cin.tie(0)->sync_with_stdio(0);
    unsigned n, q;
    std::string in;
    std::cin >> n >> q >> in;

    for (unsigned i = 0; i < q; i++) {
        unsigned qn;
        std::string needle;
        std::cin >> qn >> needle;

        std::vector<unsigned> pos;

        auto it = in.begin();
        while (true) {
            it = std::search(it, in.end(),std::boyer_moore_horspool_searcher(needle.begin(), needle.end()));
            if (it != in.end()) {
                unsigned find = it - in.begin();
                pos.push_back(find);
                if (find + needle.size() >= in.size())
                    break;
                it += needle.size();
            } else {
                break;
            }
        }

        std::cout << pos.size() << '\n';

        std::string copy;
        unsigned cp = 0;
        for (auto p : pos) {
            copy.append(in, cp, p - cp);
            cp = p + needle.size();
        }
        copy.append(in, cp, in.size() - cp);
        in = std::move(copy);
    }
    return 0;
}