#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i=a;i<(b);++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

using un = long long;
using vuc = vector<un>;
using vol = vector<bool>;

#define REP(i, a, b) for (un i = (un)a; i < (un)b; i++)
#define FEAC(i, a) for (auto&& i : a)
#define ALL(x) (x).begin(), (x).end()
#define vec vector

using trie_set_t = priority_queue<pair<un, un>, vector<pair<un, un>>, greater<pair<un, un>>>;
using trie_t = map<string, trie_set_t>;


trie_t trie;

un N;
string input;
vuc next_ptr;
vuc prev_ptr;
vec<vuc> passing;

vuc start_index;
vuc end_index;
vol is_valid;

un Q;

un next_pos(un pos, un steps=1) {

    REP(i, 0, steps) {
        if (pos == -1) return pos;
        pos = next_ptr[pos];
    }
    return pos;
}


un prev_pos(un pos, un steps=1) {

    REP(i, 0, steps) {
        if (pos == -1) return pos;
        pos = prev_ptr[pos];
    }
    return pos;
}

void create_word(un pos, un len) {
    
    if (next_pos(pos, len-1) == -1) return;

    un id = start_index.size();

    start_index.push_back(pos);
    is_valid.push_back(true);

    string w = "";
    REP(i, 0, len) {
        w += input[pos];
        passing[pos].push_back(id);
        if (i != len-1) pos = next_ptr[pos];
    }

    end_index.push_back(pos);

    trie[w].emplace(start_index[pos], id);
}

void invalidate_pos(un pos) {

    if (pos == -1) return;
    
    FEAC(id, passing[pos]) {
        is_valid[id] = false;
    }

    next_ptr[pos] = -1;
    prev_ptr[pos] = -1;

}

void delete_str(un id){

    un start_pos = start_index[id];
    un end_pos = end_index[id];

    un after_end_pos = next_pos(end_pos);
    un before_start_pos = prev_pos(start_pos);

    un pos = start_pos;
    while(pos != after_end_pos) {
        un dalsi_pos = next_pos(pos);
        invalidate_pos(pos);
        pos = dalsi_pos;
    }

    if (before_start_pos != -1) {
        next_ptr[before_start_pos] = after_end_pos;
    }

    if (after_end_pos != -1) {
        prev_ptr[after_end_pos] = before_start_pos;
    }

    if ((before_start_pos != -1) and (after_end_pos != -1)) {

        REP(k, 0, 4) {
            REP(l, 2+k, 6){
                create_word(prev_pos(before_start_pos, k), l);
            }
        }

    }

}

void process_query(const string& q) {

    trie_set_t now_set = trie[q];
    trie[q] = {};

    un ret = 0;

    un id;
    while(not now_set.empty()) {
        tie(ignore, id) = now_set.top(); now_set.pop();

        if (not is_valid[id]) continue;

        delete_str(id);
        ret++;
    }

    cout << ret << "\n";

}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    
    cin >> N >> Q;
    cin >> input;

    next_ptr = vuc(N);

    iota(ALL(next_ptr), 1);
    next_ptr[N-1] = -1;

    prev_ptr = vuc(N);
    iota(ALL(prev_ptr), -1);
    prev_ptr[0] = -1;

    passing = vec<vuc>(N, vuc());
    REP(i, 0, N) passing[i].reserve(15);


    start_index.reserve(10*N);
    end_index.reserve(10*N);
    is_valid.reserve(10*N);


    REP(l, 1, 6) {
        REP(i, 0, N-l+1) {
            create_word(i, l);
        }
    }

    REP(counter, 0, Q) {
        un L; cin >> L;
        string s;
        cin >> s;
        process_query(s);
    }



}