#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// #define int ll
// #define endl '\n'
#define F first
#define S second
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) (int)(x).size()

int n;
string s;

void addw(int i, map<string, set<int>> & mp, vector<int> & nx) {
    string a;
    int cur = i;
    for (int j = 0; j < 5; j++) {
        if (cur >= n) break;
        a.push_back(s[cur]);
        mp[a].insert(i);
        cur = nx[cur];
    }
}

void delw(int i, map<string, set<int>> & mp, vector<int> & nx, int mnl = 1) {
    string a;
    int cur = i;
    for (int j = 0; j < 5; j++) {
        if (cur >= n) break;
        a.push_back(s[cur]);
        if (sz(a) >= mnl)
            mp[a].erase(i);
        cur = nx[cur];
    }
}

void tc() {
    int q;
    cin >> n >> q;
    cin >> s;
    map<string, set<int>>mp;
    vector<int> nx(n), pr(n);
    iota(all(nx), 1);
    iota(all(pr), -1);
    for (int i  = 0; i < n; i++) {
        addw(i, mp, nx);
    }
    while (q--) {
        int x; cin >> x;
        string a;
        cin >> a;
        if (!mp.count(a)) {
            cout << 0 << endl;
            continue;
        }
        int idx = 0, ans = 0;
        auto cp = mp[a];
        for (auto x : cp) {
            if (x < idx) continue;
            ++ans;

            idx = x;
            for (int i = 0; i < sz(a) && i < n; i++)
                idx = nx[idx];

            int st = x;
            int oo = 0;
            for (int i = 0; i < 4 && pr[st] != -1; i++) {
                st = pr[st];
                ++oo;
            }
            
            int cur = st;
            while (cur != idx) {
                delw(cur, mp, nx, oo + 1);
                --oo;
                cur = nx[cur];
            }
    
            int stt = pr[x];
            if (idx != n) pr[idx] = stt;
            if (stt != -1) nx[stt] = idx;

            while (st != x && st != idx) {
                addw(st, mp, nx);
                st = nx[st];
            }
        }
        cout << ans << endl;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    tc();
}